tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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));
	}
}