题目 题意: 把对应询问区间内的数字分成很多个组，要求每个组内的数字的id,val必须是连续的。假设某个组的数字数为k，则该组的价值是k*k，让你输出总价值最大的分法对应分的区间个数。 思路: 根据vis[k+1],vis[k-1]。来判断每一次移动对res的影响。具体见add,del函数。k是a[x]离散化后对应的refl。
//1388MS 5700K #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #define en '\n' #define foru(i,a,b) for(int i=a;i<=b;++i) #define low(i) i&-i #define m(a,b) memset(a,b,sizeof a) using namespace std; typedef long long ll; const int N=1e5+5,M=N,INF=0x3f3f3f3f; template<class T>void rd(T &x) { x=0;int f=0;char ch=getchar(); while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x=f?-x:x; return; } int pos[N],tot;ll refl[N],a[N]; int bl[N],dexl,dexr,block;ll res; ll ans[M]; int vis[N]; struct Query{int id,l,r;}q[M]; bool cmp(Query x,Query y) { if(x.l/block==y.l/block) return x.r<y.r; return x.l/block<y.l/block; } void add(int x) { int k=pos[x],f1=0,f2=0; vis[k]++; if(vis[k]>1) return; if(k!=tot) f1=vis[k+1]; if(k!=1) f2=vis[k-1]; if(f1&&f2)//左右都存在 --res; if(!f1&&!f2)//左右都不存在 ++res; } void del(int x) { int k=pos[x],f1=0,f2=0; vis[k]--; if(vis[k]) return; if(k!=tot) f1=vis[k+1]; if(k!=1) f2=vis[k-1]; if(f1&&f2)//左右都存在 ++res; if(!f1&&!f2)//左右都不存在 --res; } int main() { int T;rd(T); while(T--) { m(vis,0); int n,m;rd(n),rd(m);block=sqrt(n); foru(i,1,n) rd(a[i]),refl[i]=a[i]; sort(refl+1,refl+n+1); tot=unique(refl+1,refl+n+1)-(refl+1); foru(i,1,n) pos[i]=lower_bound(refl+1,refl+tot+1,a[i])-refl; foru(i,1,m) rd(q[i].l),rd(q[i].r),q[i].id=i; sort(q+1,q+m+1,cmp); dexl=1,dexr=0,res=0; foru(i,1,m) { while(dexr<q[i].r) add(++dexr); while(dexl>q[i].l) add(--dexl); while(dexr>q[i].r) del(dexr--); while(dexl<q[i].l) del(dexl++); ans[q[i].id]=res; } foru(i,1,m) printf("%lld\n",ans[i]); } }