題目鏈接
一開始沒看數據量，直接寫了一發差分，tle了。
后來改的線段樹，結果在測試的時候顯示內存超限。
題目中說，m只有1000的數據量，但是n卻是1e6的數據量，所以從m出發去考慮問題。
我們直接離散化之后，數據量遠遠小于1e6了。這樣在利用差分數組去解決問題，遇到奇數便計數。
代碼如下：

#include<bits/stdc++.h> #define ll long long using 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)/~

總結

以上是生活随笔為你收集整理的Light bulbs（上海icpc网络预选赛，差分离散化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。