本文共 939 字，大约阅读时间需要 3 分钟。
一开始没看数据量，直接写了一发差分，tle了。 后来改的线段树，结果在测试的时候显示内存超限。 题目中说，m只有1000的数据量，但是n却是1e6的数据量，所以从m出发去考虑问题。 我们直接离散化之后，数据量远远小于1e6了。这样在利用差分数组去解决问题，遇到奇数便计数。 代码如下：#include#define ll long longusing namespace std;const int maxx=1e6+100;struct node{ int x,y;}p[1010];int a[maxx];int c[maxx];int n,m;int main(){ int t,x,y,pos1,pos2,k=0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); int cnt=0; memset(c,0,sizeof(c)); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); x++,y++; a[++cnt]=x;a[++cnt]=y;a[++cnt]=y+1; p[i].x=x;p[i].y=y; } sort(a+1,a+1+cnt); int len=unique(a+1,a+1+cnt)-a-1;//离散化，去重 int sum=0; for(int i=1;i<=m;i++) { pos1=lower_bound(a+1,a+1+len,p[i].x)-a; pos2=lower_bound(a+1,a+1+len,p[i].y+1)-a; c[pos1]++,c[pos2]--; } for(int i=1;i<=len;i++) { c[i]+=c[i-1]; if(c[i]&1) sum+=a[i+1]-a[i];//遇到奇数后，这个位置之后的，到下一个位置之前的灯都是操作奇数次的，加上就好了。 } printf("Case #%d: %d\n",++k,sum); }}
努力加油a啊，(o)/~
转载地址：http://uutvi.baihongyu.com/