1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<queue>
 7 #define lson l,mid,rt<<1
 8 #define rson mid+1,r,rt<<1|1
 9 #define root 1,n,1
10 #define mid ((l+r)>>1)
11 #define ll long long
12 #define cl(a) memset(a,0,sizeof(a))
13 #define ts printf("*****\n");
14 using namespace std;
15 const int MAXN=199999+9;
16 int sum[MAXN<<2],lsum[MAXN<<2],rsum[MAXN<<2],lc[MAXN<<2],rc[MAXN<<2];
17 int n,m,t;
18 void pushup(int rt,int m)
19 {
20     lc[rt]=lc[rt<<1];
21     rc[rt]=rc[rt<<1|1];
22     lsum[rt]=lsum[rt<<1];
23     rsum[rt]=rsum[rt<<1|1];
24     sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
25     if(rc[rt<<1]!=lc[rt<<1|1])
26     {
27         sum[rt]=max(sum[rt],rsum[rt<<1]+lsum[rt<<1|1]);
28 
29         if(sum[rt<<1]==(m-(m>>1)))
30         {
31             lsum[rt]=sum[rt<<1]+lsum[rt<<1|1];
32         }
33         if(sum[rt<<1|1]==(m>>1))
34         {
35             rsum[rt]=sum[rt<<1|1]+rsum[rt<<1];
36         }
37     }
38 }
39 void build(int l,int r,int rt)
40 {
41     sum[rt]=lsum[rt]=rsum[rt]=lc[rt]=rc[rt]=1;
42     if(l==r)    return;
43     build(lson);
44     build(rson);
45 }
46 void update(int pos,int l,int r,int rt)
47 {
48     if(l==r)
49     {
50         lc[rt]=rc[rt]^=1;
51         return;
52     }
53     if(pos<=mid)  update(pos,lson);
54     if(pos>mid)  update(pos,rson);
55     pushup(rt,(r-l+1));
56 }
57 int main()
58 {
59     int i,j,k,q;
60     scanf("%d%d",&n,&m);
61     build(root);
62     int pos;
63     for(i=0;i<m;i++)
64     {
65         scanf("%d",&pos);
66         update(pos,root);
67         printf("%d\n",sum[1]);
68     }
69     return 0;
70 }

题解代码

 1 #include<cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define mid (l+r)/2
 5 #define ls rt<<1,l,mid
 6 #define rs rt<<1|1,mid+1,r
 7 using namespace std;
 8 const int Rn=199999+9;
 9 int N,Q;
10 struct Node
11 {
12     int lc,rc;  //左右两端颜色
13     int ln,rn;  //左右两边长度
14     int val;    //长度
15 }T[Rn<<2];
16 void pushup(int rt,int l,int r)
17 {
18     Node &x1=T[rt],x2=T[rt<<1],x3=T[rt<<1 | 1];
19     x1.lc=x2.lc;
20     x1.rc=x3.rc;
21     x1.ln=x2.ln;
22     x1.rn=x3.rn;
23     x1.val=max(x2.val,x3.val);
24     if(x2.rc!=x3.lc)
25     {
26         x1.val=max(x1.val,x2.rn+x3.ln);
27         if(x2.val==mid-l+1){
28             x1.ln=x2.val+x3.ln;
29         }
30         if(x3.val==r-mid){
31             x1.rn=x3.val+x2.rn;
32         }
33     }
34 
35 }
36 void build(int rt,int l,int r)
37 {
38     Node &S=T[rt];
39     S.lc=S.rc=S.ln=S.rn=S.val=1;
40     if(l==r)
41     {
42         return;
43     }
44     build(ls);
45     build(rs);
46 }
47 
48 void update(int rt,int l,int r,int x)
49 {
50     if(l==r)
51     {
52         T[rt].lc=T[rt].rc=T[rt].lc^1;
53         return;
54     }
55     if(x<=mid)
56     {
57         update(ls,x);
58     }
59     if(x>mid)
60     {
61         update(rs,x);
62     }
63     pushup(rt,l,r);
64 }
65 
66 int main()
67 {
68     #ifndef ONLINE_JUDGE
69     freopen("1.in","r",stdin);
70     #endif
71     int x;
72     scanf("%d%d",&N,&Q);
73     build(1,1,N);
74     for(int i=0;i<Q;i++)
75     {
76         scanf("%d",&x);
77         update(1,1,N,x);
78         printf("%d\n",T[1].val);
79     }
80     return 0;
81 
82 }

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。