1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include <bits/stdc++.h> #define MAXN 50005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } namespace SegmentTree{ struct node{ int l,r,val; int lmax,rmax,maxn; inline int len(){ return r-l+1; } }tree[MAXN<<2]; #define lc i<<1 #define rc i<<1|1 inline void Change(int i){ tree[i].lmax=1-tree[i].lmax; tree[i].rmax=1-tree[i].rmax; tree[i].maxn=1-tree[i].maxn; tree[i].val=1-tree[i].val; } inline void pushup(int i){ tree[i].val=tree[lc].val+tree[rc].val; tree[i].lmax=tree[lc].lmax; if (tree[lc].val==tree[lc].len()) tree[i].lmax=max(tree[i].lmax,tree[lc].len()+tree[rc].lmax); tree[i].rmax=tree[rc].rmax; if (tree[rc].val==tree[rc].len()) tree[i].rmax=max(tree[i].rmax,tree[rc].len()+tree[lc].rmax); tree[i].maxn=max(max(tree[lc].maxn,tree[rc].maxn),tree[lc].rmax+tree[rc].lmax); } void Update(int i,int l,int r,int pos){ if (l==r){ Change(i); return ; } int mid=(l+r)>>1; if (pos<=mid) Update(lc,l,mid,pos); else Update(rc,mid+1,r,pos); pushup(i); } void Build(int i,int l,int r){ tree[i].l=l,tree[i].r=r; if (l==r){ return ; } int mid=(l+r)>>1; Build(lc,l,mid); Build(rc,mid+1,r); } } using namespace SegmentTree; int a[MAXN],pos[MAXN]; struct Query{ int l,r,id; }q[MAXN]; inline bool operator < (const Query &a,const Query &b){ return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r)); } int Ans[MAXN]; int main(){ int n=read(),m=read(); int Size=sqrt(n); for (register int i=1;i<=n;++i){ a[i]=read(); pos[i]=(i-1)/Size+1; } for (register int i=1;i<=m;++i){ q[i].l=read(),q[i].r=read(),q[i].id=i; } sort(q+1,q+1+m); int l=1,r=0; Build(1,1,n); for (register int i=1;i<=m;++i){ while (l<q[i].l) Update(1,1,n,a[l++]); while (l>q[i].l) Update(1,1,n,a[--l]); while (r<q[i].r) Update(1,1,n,a[++r]); while (r>q[i].r) Update(1,1,n,a[r--]); Ans[q[i].id]=tree[1].maxn; } for (register int i=1;i<=m;++i){ printf("%d\n",Ans[i]); } }
|