题解 | #[NOIP2007]字符串的展开#

采用差分数组的解法网上已经有很多了，这里我不再赘述。
这里采用的方式是差分数组离散化的思想，针对每个端点仓库进行记录。
每次进货产生左右两个端点进货信息。

#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
struct temp//定义一个结构体，存储每次进货信息
{
    int pos;//端点仓库编号
    ll d;//进货商品编号
    int state;//左端点为+1，右端点为-1
}a[200005];
bool comp(temp a,temp b)
{
    if(a.pos<b.pos) return 1;//按仓库编号对进货信息升序
    else if(a.pos==b.pos) return a.state<b.state;//如果两次进货信息端点仓库编号相同应先处理上一次进货信息的右端点，避免多算
    else return 0;
}
int main()
{
    int n,m,j=1;
    int l,r;ll d;
    cin>>n>>m;
    for(int i = 1;i<=m;i++)
    {
        scanf("%d %d %lld",&l,&r,&d);
        a[j].pos = l;a[j].d = d;a[j].state = 1;//录入本次进货左端点信息
        j += 1; 
        a[j].pos = r+1;a[j].d = d;a[j].state = -1;//录入本次进货右端点信息
        j += 1;
    }
    sort(a+1,a+1+2*m,comp);
    int cnt = 0,max = 0,max_pos = 0,size;
    map <ll,int> s;//存储每个商品进货次数，以便遇到右端点处理时减去，最开始是用set来写的，没存储进货次数，导致商品在遇到第一个右端点时就找不到了，后面本来可以覆盖的也覆盖不到了
    map <ll,int> :: iterator it;
    for(int i = 1;i<=2*m;i++)
    {
		size = s.size();//记录本次进货前商品种类数
        if(a[i].state==1)//进货左端点
        {
           it=s.find(a[i].d);
           if(it!=s.end()) it->second = it->second+1;//判断是否已进过本商品，进过则次数加一
           else 
		   {
			   s.insert({a[i].d,1});//没进过则记录该商品，并将进货次数置为1
		       if((cnt =s.size())>size)//判断商品种类数是否增大，（这里可以删除）
		        {
		            if(cnt>max)//判断进完该商品，商品种类数是否大于最大值，是则更新最大值信息
		            {
		            	max =cnt;
		            	max_pos = a[i].pos;
		            }
		        }
		   }
        }
        else//进货右端点
        {
           it=s.find(a[i].d);
           if(it!=s.end()) it->second = it->second-1;//找到该商品并将进货次数-1
            if(it->second==0)//如果此时进货次数为零，意味着从该位置开始后面的仓库不再有该商品
            {
                s.erase(it);//删除该商品信息
                cnt--;当前商品种类数-1
            }
        }
    }
    cout<<max_pos;
    return 0;
}