POJ3368 (C++)

poj3368.cpp

#include <stdio.h>
#include <string.h>

const int maxn=100010;

struct segment {
  int left,right;
	int count;
} a[maxn*2];
int f[maxn],k;

int max(int p, int q) {
	return p>q?p:q;
}

void segtree_create(int p, int l, int r);
void segtree_insert(int p, int l, int r, int c);
int segtree_query(int p, int l, int r);
inline int search_left(int p);
inline int search_right(int p);

int main() {
	int n,q;
	scanf("%d",&n);
	while (n) {
		scanf("%d",&q);
		memset(a,0,sizeof(a));
		memset(f,0,sizeof(f));
		int t,temp;
		k=0;
		scanf("%d",&t);
		for (int i=2; i<=n; i++) {
			scanf("%d",&temp);
			if (temp!=t) f[++k]=i-1;
			t=temp;
		}
		f[++k]=n;
		segtree_create(1,0,k);
		for (int i=1; i<=k; i++) segtree_insert(1,i-1,i,f[i]-f[i-1]);
		int l,r;
		for (int i=0; i<q; i++) {
			scanf("%d%d",&l,&r);
			l--;
			int p=search_left(l),q=search_right(r);
			if (p>q) {
				printf("%d\n",r-l);
				continue;
			}
			int ans=max(f[p]-l,r-f[q]);
			if (q-p>0) ans=max(ans,segtree_query(1,p,q));
			printf("%d\n",ans);
		}
		scanf("%d",&n);
	}
	return 0;
}

void segtree_create(int p, int l, int r) {
	a[p].left=l;
	a[p].right=r;
	a[p].count=0;
	if (r-l==1) return;
	int m=(l+r)>>1;
	segtree_create(p*2,l,m);
	segtree_create(p*2+1,m,r);
}

void segtree_insert(int p, int l, int r, int c) {
	if (a[p].left==l && a[p].right==r) {
		a[p].count=c;
		return;
	}
	int m=(a[p].left+a[p].right)>>1;
	if (r<=m) segtree_insert(p*2,l,r,c); else segtree_insert(p*2+1,l,r,c);
	a[p].count=max(a[p*2].count,a[p*2+1].count);
}

int segtree_query(int p, int l, int r) {
	if (a[p].left==l && a[p].right==r) return a[p].count;
	int m=(a[p].left+a[p].right)>>1;
	if (r<=m) return segtree_query(p*2,l,r); else 
		if (l>=m) return segtree_query(p*2+1,l,r); else 
			return max(segtree_query(p*2,l,m),segtree_query(p*2+1,m,r));
	return 0;
}

inline int search_left(int p) {
	if (p==f[0]) return 0;
	int l=0,r=k;
	while (l<=r) {
		int m=(l+r)>>1;
		if (f[m]>=p && f[m-1]<p) return m;
		if (f[m]>p) r=m; else l=m+1;
	}
	return r;
}

inline int search_right(int p) {
	int l=0,r=k;
	if (p==f[k]) return k;
	while (l<=r) {
		int m=(l+r)>>1;
		if (f[m]<=p && f[m+1]>p) return m;
		if (f[m]>p) r=m; else l=m+1;
	}
	return l;
}