1 5 2 3 1 2 5 4 1 5 2 4
1 2
题意：
给你一个长度为n(1<=n<=100000)的数列。数列中的值互不相同且1<=ai<=n。对于一个给定的区间。[L,R]ans就为
下标[L,R]的数。中取值连续的块的块数。比如。1,3,2,6,8,7块数就为2。1,2,3一块。6,7,8为一块。
思路：
由于知道[L,R]的答案可以得到附近区间的答案。就想用莫队水一发。但是维护区间内有多少块是用线段树维护的。结果不言而喻。。其实不用线段树的。直接开个bool数组。如果i出现了就把vis[i]置为1.判断块数就简单了。加入一个数的时候如果vis[i-1]和vis[i+1]都为1的话那么块数ans就要-1.如果只有一个为1的话ans不变。如果全为0的话ans+1.
删除一个数类似处理就行了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
struct qnode
{
int l,r,idx;
} qu[maxn];
int id[maxn],pos[maxn],ans[maxn],bks;
bool vis[maxn];
bool cmp(qnode a,qnode b)
{
if(pos[a.l]==pos[b.l])
return a.r<b.r;
return pos[a.l]<pos[b.l];
}
void update(int x,bool d)
{
vis[x]=d;
if(d)
bks+=1-vis[x-1]-vis[x+1];
else
bks+=vis[x-1]+vis[x+1]-1;
}
int main()
{
int t,n,m,i,j,bk,pl,pr,pp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
memset(vis,0,sizeof vis);
bk=ceil(sqrt(1.0*n));
for(i=1;i<=n;i++)
{
scanf("%d",&id[i]);
pos[i]=(i-1)/bk;
}
for(i=0;i<m;i++)
{
scanf("%d%d",&qu[i].l,&qu[i].r);
qu[i].idx=i;
}
sort(qu,qu+m,cmp);
pl=1,pr=0,bks=0;
for(i=0;i<m;i++)
{
pp=qu[i].idx;
if(pr<qu[i].r)
{
for(j=pr+1;j<=qu[i].r;j++)
update(id[j],1);
}
else
{
for(j=pr;j>qu[i].r;j--)
update(id[j],0);
}
if(pl<qu[i].l)
{
for(j=pl;j<qu[i].l;j++)
update(id[j],0);
}
else
{
for(j=pl-1;j>=qu[i].l;j--)
update(id[j],1);
}
pl=qu[i].l,pr=qu[i].r;
ans[pp]=bks;
}
for(i=0;i<m;i++)
printf("%d\n",ans[i]);
}
return 0;
}
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
struct qnode
{
int l,r,idx;
} qu[maxn];
int id[maxn],bks[maxn<<1],ml[maxn<<1],mr[maxn<<1],pos[maxn],ans[maxn];
bool cmp(qnode a,qnode b)
{
if(pos[a.l]==pos[b.l])
return a.r<b.r;
return pos[a.l]<pos[b.l];
}
void build(int L,int R,int rt)
{
bks[rt]=ml[rt]=mr[rt]=0;
if(L==R)
return;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void update(int L,int R,int rt,int p,int d)
{
if(L==R)
{
bks[rt]=ml[rt]=mr[rt]=d;
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(p<=mid)
update(lson,p,d);
else
update(rson,p,d);
bks[rt]=bks[ls]+bks[rs];
ml[rt]=ml[ls];
mr[rt]=mr[rs];
if(mr[ls]&&ml[rs])
bks[rt]--;
}
int qubks(int L,int R,int rt,int l,int r)
{
if(l<=L&&R<=r)
return bks[rt];
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1,tp=0,ct=0;
if(l<=mid)
tp+=qubks(lson,l,r),ct++;
if(r>mid)
tp+=qubks(rson,l,r),ct++;
if(ct==2&&mr[ls]&&ml[rs])
tp--;
return tp;
}
int main()
{
int t,n,m,i,j,bk,pl,pr,pp;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(1,n,1);
bk=ceil(sqrt(1.0*n));
for(i=1;i<=n;i++)
{
scanf("%d",&id[i]);
pos[i]=(i-1)/bk;
}
for(i=0;i<m;i++)
{
scanf("%d%d",&qu[i].l,&qu[i].r);
qu[i].idx=i;
}
sort(qu,qu+m,cmp);
pl=1,pr=0;
for(i=0;i<m;i++)
{
pp=qu[i].idx;
if(pr<qu[i].r)
{
for(j=pr+1;j<=qu[i].r;j++)
update(1,n,1,id[j],1);
}
else
{
for(j=pr;j>qu[i].r;j--)
update(1,n,1,id[j],0);
}
if(pl<qu[i].l)
{
for(j=pl;j<qu[i].l;j++)
update(1,n,1,id[j],0);
}
else
{
for(j=pl-1;j>=qu[i].l;j--)
update(1,n,1,id[j],1);
}
pl=qu[i].l,pr=qu[i].r;
ans[pp]=qubks(1,n,1,1,n);
}
for(i=0;i<m;i++)
printf("%d\n",ans[i]);
}
return 0;
}
原文：http://blog.csdn.net/bossup/article/details/39236227