题目地址：HDU 4638 先写了一发莫队，莫队可以水过。很简单的莫队，不多说。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;int a[MAXN];LL ha[MAXN], ans[MAXN], res;struct node {int l, r, id, pos;} fei[MAXN];bool cmp(node x, node y){return x.pos<y.pos||x.pos==y.pos&&x.r<y.r;}void reduce(int tmp){if(ha[tmp-1]&&ha[tmp+1]) res++;else if(!ha[tmp-1]&&!ha[tmp+1]) res–;ha[tmp]=0;}void add(int tmp){if(ha[tmp-1]&&ha[tmp+1]) res–;else if(!ha[tmp-1]&&!ha[tmp+1]) res++;ha[tmp]=1;}int main(){int t, n, m, i, j, k, tmp, l, r;scanf(“%d”,&t);while(t–) {scanf(“%d%d”,&n,&m);for(i=1; i<=n; i++) {scanf(“%d”,&a[i]);}k=sqrt(n*1.0);for(i=0; i<m; i++) {scanf(“%d%d”,&fei[i].l,&fei[i].r);fei[i].id=i;fei[i].pos=fei[i].l/k;}sort(fei,fei+m,cmp);memset(ha,0,sizeof(ha));l=1;r=0;res=0;for(i=0; i<m; i++) {while(r>fei[i].r) {tmp=a[r];reduce(tmp);r–;}while(r<fei[i].r) {r++;tmp=a[r];add(tmp);}while(l<fei[i].l) {tmp=a[l];reduce(tmp);l++;}while(l>fei[i].l) {l–;tmp=a[l];add(tmp);}ans[fei[i].id]=res;}for(i=0; i<m; i++) {printf(“%I64d\n”,ans[i]);}}return 0;}
然后又看了解题报告，发现线段树+离线查询也可以过。而且感觉很神奇的做法。。 首先先离线保存下来。然后从左向右维护，维护的是前面的值对于当前枚举值的相对个数。对于当前第i个数来说，先将这个数的值更新为1，代表一个独立的串，然后找a[i]-1和a[i]+1前面存在不存在，，如果存在的话，则说明前面的这两个数已经不能作为独立的串了，相对于a[i]来说，可以共存在a[i]的串中，所以就要将a[i]-1和a[i]+1分别-1.然后再在r值为i的询问中，直接线段树求和就可以了。代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;int a[MAXN], pos[MAXN], sum[MAXN<<2], ans[MAXN];struct node{int l, r, id;}fei[MAXN];bool cmp(node x, node y){return x.r<y.r;}void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void Update(int p, int x, int l, int r, int rt){if(l==r){sum[rt]+=x;return ;}int mid=l+r>>1;if(p<=mid) Update(p,x,lson);else Update(p,x,rson);PushUp(rt);}int Query(int ll, int rr, int l, int r, int rt){if(ll<=l&&rr>=r){return sum[rt];}int mid=l+r>>1, ans=0;if(ll<=mid) ans+=Query(ll,rr,lson);if(rr>mid) ans+=Query(ll,rr,rson);return ans;}int main(){int t, n, m, i, j;scanf(“%d”,&t);while(t–){scanf(“%d%d”,&n,&m);for(i=1;i<=n;i++){scanf(“%d”,&a[i]);pos[a[i]]=i;}for(i=0;i<m;i++){scanf(“%d%d”,&fei[i].l,&fei[i].r);fei[i].id=i;}memset(sum,0,sizeof(sum));sort(fei,fei+m,cmp);j=0;for(i=1;i<=n;i++){Update(i,1,root);if(a[i]>1&&pos[a[i]-1]<i) Update(pos[a[i]-1],-1,root);if(a[i]<n&&pos[a[i]+1]<i) Update(pos[a[i]+1],-1,root);while(j<m&&fei[j].r<=i){ans[fei[j].id]=Query(fei[j].l,i,root);j++;}}for(i=0;i<m;i++){printf(“%d\n”,ans[i]);}}return 0;}
当世界给草籽重压时，它总会用自己的方法破土而出。
