19.98%
1000ms
8192K
There are NN light bulbs indexed from 00 to N-1N?1. Initially, all of them are off.

A FLIP operation switches the state of a contiguous subset of bulbs. FLIP(L, R)FLIP(L,R)means to flip all bulbs xx such that L \leq x \leq RL≤x≤R. So for example, FLIP(3, 5)FLIP(3,5) means to flip bulbs 33 , 44 and 55, and FLIP(5, 5)FLIP(5,5) means to flip bulb 55.

Given the value of NN and a sequence of MMflips, count the number of light bulbs that will be on at the end state.

InputFile
The first line of the input gives the number of test cases, TT. TT test cases follow. Each test case starts with a line containing two integers NN and MM, the number of light bulbs and the number of operations, respectively. Then, there are MMmore lines, the ii-th of which contains the two integers L_iLi? and R_iRi?, indicating that the ii-th operation would like to flip all the bulbs from L_iLi? to R_iRi? , inclusive.

1 \leq T \leq 10001≤T≤1000

1 \leq N \leq 10^61≤N≤106

1 \leq M \leq 10001≤M≤1000

0 \leq L_i \leq R_i \leq N-10≤Li?≤Ri?≤N?1

OutputFile
For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 11) and yy is the number of light bulbs that will be on at the end state, as described above.

樣例輸入復制

2
10 2
2 6
4 8
6 3
1 1
2 3
3 4
樣例輸出復制

Case #1: 4
Case #2: 3

題目大意：
先輸入一個整數$T(1\le T\le 1000)$，代表有$T$組測試數據，對于每組測試數據，先輸入兩個整數$n(1\le n\le 1e6),m(1\le m\le 1000)$，代表有$n$個燈泡，初始狀態全為滅，$m$次操作，下面$m$行每行輸入兩個整數$l,r$，代表將從第$l$個燈泡到第$r$個燈泡的狀態全部反轉，即開著的燈泡滅掉，滅掉的燈泡打開，問經過$m$次操作后最終有多少燈泡是打開的。

解題思路：
如果是普通差分然后暴力跑一遍的話時間復雜度為$1e9$，會超時。
所以此題可以將每次操作的兩個端點存起來，按端點從小到大排好序，對于每次的$l$，可以認為后面的操作均加$1$，對于$r$，可認為均減$1$，因此這樣就可以把區間拆分成連續不相交的短區間。

代碼：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
struct node
{int id;int f;
}arr[2100];
int cnt=0;
bool cmp(node a,node b) {return a.id<b.id;
}
int main() 
{#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif//ios::sync_with_stdio(0),cin.tie(0);int T;scanf("%d",&T);rep(t,1,T) {int n,m;int l,r;scanf("%d %d",&n,&m);cnt=0;rep(i,1,m) {scanf("%d %d",&l,&r);arr[++cnt].id=l;arr[cnt].f=1;arr[++cnt].id=r+1;arr[cnt].f=0;}sort(arr+1,arr+1+cnt,cmp);int ans=0;int nape=0;for(int i=1;i<cnt;i++) {if(arr[i].f==1) nape++;else nape--;if(nape&1) {ans+=(arr[i+1].id-arr[i].id);}}printf("Case #%d: %d\n",t,ans);}return 0;
}