这个题超级水吧，但是想做出来还是得花不少时间，一开始想着先排序，X小的在前面，互相交换各自SET里面的东西，这样每个SET数组的size就是能得到最后的总的东西了，这样的话数据量20万输入进SET大概400亿算了算不行，后来发现既然全都挨着为何不只存最大和最小呢，要是codeforce数据不水我肯定完，谨慎使用吧·1
但是自我认为这种思想很对。。。代码就是模拟过程
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <set> using namespace std; struct node { int x,y; } no[100010]; bool cmp(node a, node b) { return a.x < b.x; } set<int> se[200010]; set<int>::iterator it; int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 0 ; i < n ; i++) { se[i].insert(i); } for(int i =0 ; i < m ; i ++) { scanf("%d%d",&no[i].x, &no[i].y); } sort(no,no+m,cmp); for(int i =0 ; i < m ; i++) { int op = no[i].y; int mmax1 = 0,mmin1 = 2000000; int mmax2 = 0,mmin2 = 2000000; for(it = se[op].begin(); it != se[op].end(); it++) { mmax1 = max(*it,mmax1); mmin1 = min(*it,mmin1); } for(it = se[op-1].begin(); it != se[op-1].end(); it++) { mmax2 = max(*it,mmax2); mmin2 = min(*it,mmin2); } int mmax = max(mmax1,max(mmax2,max(mmin1,mmin2))); int mmin = min(mmax1,min(mmax2,min(mmin1,mmin2))); se[op].clear(); se[op-1].clear(); se[op].insert(mmax); se[op].insert(mmin); se[op-1].insert(mmax); se[op-1].insert(mmin); } for(int i = 0; i < n ; i++) { int mmax1 = 0,mmin1 = 2000000; for(it = se[i].begin(); it != se[i].end(); it++) { mmax1 = max(*it,mmax1); mmin1 = min(*it,mmin1); } int siz = mmax1-mmin1+1; if(i == 0) printf("%d",siz); else printf(" %d",siz); } return 0; }