题目描述
在一条数轴上有N个点，分别是1—N。一开始所有的点都被染成黑色。接着我们进行M次操作，第i次操作将[Li，Ri]这些点染成白色。请输出每个操作执行后剩余黑色点的个数。
输入格式
输入一行为N和M。下面M行每行两个数Li、Ri。
输出格式
输出M行，为每次操作后剩余黑色点的个数。
输入输出样例
输入 #1
10 3
3 3
5 7
2 8
输出 #1
9
6
3
说明/提示
对于30%的数据，有1≤N≤2000，1≤M≤2000;
分块
代码：
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define N 200100
using namespace std;
int pos[N],le[N],ri[N],tag[N],sum,n,m,a[N];
int query(int l,int r)
{
if(pos[l]==pos[r])
{
if(tag[pos[l]])
for(int i=l;i<=r;i++)
{
if(a[i])a[i]=0,tag[pos[i]]--,sum--;
}
}
else
{
if(tag[pos[l]])
for(int i=l;i<=ri[pos[l]];i++)
if(a[i])a[i]=0,tag[pos[l]]--,sum--;
for(int i=pos[l]+1;i<=pos[r]-1;i++)
{
sum-=tag[i];tag[i]=0;
}
if(tag[pos[r]])
for(int i=le[pos[r]];i<=r;i++)
{
if(a[i])a[i]=0,tag[pos[r]]--,sum--;
}
}
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
int len=sqrt(n);
sum=n;
for(int i=1;i<=n;i++)a[i]=1;
for(int i=1;i<=n;i++)pos[i]=(i-1)/len+1;
for(int i=1;i<=pos[n];i++)
{
le[i]=(i-1)*len+1;
ri[i]=min(n,i*len);
tag[i]=ri[i]-le[i]+1;
}
for(int i=1,l,r;i<=m;i++)
{
scanf("%d%d",&l,&r);
int ans=query(l,r);
printf("%d
",ans);
}
return 0;
}