本文共 2109 字，大约阅读时间需要 7 分钟。
题意O(-1)不用解释。。
线段树结点维护三个信息：区间内相同的数出现最多的次数maxc、区间左边第一个数出现的次数lc、区间右边第一个数出现的次数rc。
分左区间右端点和右区间左端点相同于否的情况合并区间，注意lc或rc为区间长度的情况。
//#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef pair pii;#define pb(a) push_back(a)#define INF 0x1f1f1f1f#define lson idx<<1,l,mid#define rson idx<<1|1,mid+1,r#define PI 3.1415926535898template T min(const T& a,const T& b,const T& c){ return min(min(a,b),min(a,c));}template T max(const T& a,const T& b,const T& c){ return max(max(a,b),max(a,c));}void debug(){#ifdef ONLINE_JUDGE#else freopen("d:\\in.txt","r",stdin); freopen("d:\\out1.txt","w",stdout);#endif}char getch(){ char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!='\n')return ch; } return EOF;}const int maxn=100100;struct node{ int lc,rc,maxc; node (int a,int b,int c):lc(a),rc(b),maxc(c){} node(){}}tree[maxn<<2];int da[maxn];int PushUp(node &q,node &q1,node &q2,int l,int r){ int mid=(r+l)>>1; if(da[mid]!=da[mid+1]) { q.maxc=max(q1.maxc,q2.maxc); q.lc=q1.lc; q.rc=q2.rc; }else { q.maxc=max(q1.maxc,q2.maxc,q1.rc+q2.lc); q.lc=q1.lc==mid-l+1?q1.lc+q2.lc:q1.lc; q.rc=q2.rc==r-mid?q2.rc+q1.rc:q2.rc; } return 0;}int build(int idx,int l,int r){ if(l==r) { tree[idx]=node(1,1,1); return 0; } int mid=(r+l)>>1; build(lson); build(rson); PushUp(tree[idx],tree[idx<<1],tree[idx<<1|1],l,r); return 0;}node quary(int idx,int l,int r,int tl,int tr){ if(tl<=l&&tr>=r) return tree[idx]; int mid=(r+l)>>1; node q1,q2; node q; if(mid>=tl&&mid mid)q=quary(rson,tl,tr); } return q;}int main(){ int n,q; while(scanf("%d",&n)!=EOF&&n) { scanf("%d",&q); for(int i=1;i<=n;i++) scanf("%d",&da[i]); da[0]=INT_MIN;da[n+1]=INT_MAX; build(1,1,n); for(int i=1;i<=q;i++) { int a,b; scanf("%d%d",&a,&b); node x=quary(1,1,n,a,b); printf("%d\n",x.maxc); } } return 0;}
转载于:https://www.cnblogs.com/BMan/p/3257042.html
