PKU3419 Difference Is Beautiful
数年間の誤読の末AC. PKUの中でも超良問の類だと思う。両端の強引な帳尻合わせが最高にCool.
#include<stdio.h> #include<algorithm> using namespace std; int segtree[524288]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return -99999999; if(c<=a&&b<=d)return segtree[e]; return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1)); } void update(int a,int b){ a+=262144; while(a){ segtree[a]=max(b,segtree[a]); a/=2; } } int c[210000]; int at[2100000]; int v[210000]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){scanf("%d",c+i);c[i]+=1000000;} update(a-1,1); int now=a-1; for(int i=0;i<2100000;i++)at[i]=a; at[c[a-1]]=a-1; v[a-1]=a-1; for(int i=a-2;i>=0;i--){ now=min(now,at[c[i]]-1); at[c[i]]=i; update(i,now-i+1); v[i]=now; } for(int i=0;i<b;i++){ int d,e;scanf("%d%d",&d,&e); int val=lower_bound(v+d,v+a,e)-v; printf("%d\n",max(query(0,262143,d,min(e,val-1),1),e-val+1)); } }