首页 > 代码库 > BZOJ4750 密码安全

BZOJ4750 密码安全

题意:

给一序列求解

$$\sum_{L=1}^n{ \sum_{R=L}^n{ max(a_L,a_{L+1},...,a_R) * (a_L \oplus a_{L+1} \oplus ... a_R)  } }$$

 

解法:

首先注意到利用每个最大值有一个管制区间的性质,我们可以将$O(n^2)$降为$O(n)$

这样,我们用单调栈求出每个点的管制区间记做$L(i),R(i)$,那么

记$NimSum(l,r) = a_l \oplus a_{l+1} \oplus ... a_r$

则有

$$answer = \sum_{x=1}^n{ a(x) * \sum_{l=L(x)}^x { \sum_{r=x}^{R(x)}{NimSum(l,r)} } }$$

接下来考虑快速求解 $S(x) = \sum_{l=L(x)}^x { \sum_{r=x}^{R(x)}{NimSum(l,r)} }$

注意到异或操作位与位相独立,这样考虑对于每一位进行处理则有

$S(x) = \sum_{t=0}^{30} {第t位Nim和为1 且 经过坐标x的子段个数}$

对于第$t$位$Nim$和为1 且 经过坐标$x$的子段个数,我们从小到大枚举$t$

可以考虑用线段树维护$lcnt(x,t),rcnt(x,t)$表示当前区间前缀和为$t$的前缀个数 与 后缀和为$t$的后缀个数

总效率$O(n {log}^2{n})$,TLE

技术分享
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm> 
  5 
  6 #define N 100010
  7 #define LL long long
  8 #define lb(x) ((x)&(-x))
  9 #define P 1000000061LL
 10 #define l(x) ch[x][0]
 11 #define r(x) ch[x][1]
 12 
 13 using namespace std;
 14 
 15 int n,totn;
 16 int a[N],b[N];
 17 int ch[N<<1][2],c[N],Lv[N<<1],Rv[N<<1];
 18 
 19 struct node
 20 {
 21     int s,ls[2],rs[2];
 22     LL sum;
 23 }tree[N<<1];
 24 
 25 int build(int l,int r)
 26 {
 27     int x=++totn;
 28     Lv[x]=n+1;
 29     Rv[x]=0;
 30     if(l==r) return x;
 31     int mid=(l+r)>>1;
 32     l(x)=build(l,mid);
 33     r(x)=build(mid+1,r);
 34     return x;
 35 }
 36 
 37 void add(int x,int l,int r,int qx)
 38 {
 39     if(l==r)
 40     {
 41         Lv[x]=Rv[x]=l;
 42         return;
 43     }
 44     int mid=(l+r)>>1;
 45     if(qx<=mid) add(l(x),l,mid,qx);
 46     else add(r(x),mid+1,r,qx);
 47     Lv[x] = min(Lv[l(x)], Lv[r(x)]);
 48     Rv[x] = max(Rv[l(x)], Rv[r(x)]);
 49 }
 50 
 51 node add(node L,node R)
 52 {
 53     node ans;
 54     ans.s = L.s ^ R.s;
 55     ans.ls[0] = L.ls[0] + R.ls[L.s];
 56     ans.ls[1] = L.ls[1] + R.ls[L.s^1];
 57     ans.rs[0] = R.rs[0] + L.rs[R.s];
 58     ans.rs[1] = R.rs[1] + L.rs[R.s^1];
 59     ans.sum = L.sum + R.sum;
 60     ans.sum += L.rs[0] * (LL)R.ls[1]%P;
 61     ans.sum += L.rs[1] * (LL)R.ls[0]%P;
 62     ans.sum %= P;
 63     return ans;
 64 }
 65 
 66 int build2(int l,int r)
 67 {
 68     int x=++totn;
 69     if(l==r)
 70     {
 71         tree[x].s=c[l];
 72         tree[x].ls[c[l]]=1;
 73         tree[x].ls[c[l]^1]=0;
 74         tree[x].rs[c[l]]=1;
 75         tree[x].rs[c[l]^1]=0;
 76         tree[x].sum=c[l];
 77         return x;
 78     }
 79     int mid=(l+r)>>1;
 80     l(x)=build2(l,mid);
 81     r(x)=build2(mid+1,r);
 82     tree[x] = add(tree[l(x)],tree[r(x)]);
 83     return x;
 84 }
 85 
 86 node ask(int x,int l,int r,int ql,int qr)
 87 {
 88     if(ql<=l && r<=qr) return tree[x];
 89     int mid=(l+r)>>1;
 90     if(ql<=mid && mid<qr)
 91     {
 92         node L=ask(l(x),l,mid,ql,qr);
 93         node R=ask(r(x),mid+1,r,ql,qr);
 94         return add(L,R);
 95     }
 96     if(ql<=mid)
 97         return ask(l(x),l,mid,ql,qr);
 98     return ask(r(x),mid+1,r,ql,qr);
 99 }
100 
101 int askL(int x,int l,int r,int ql,int qr)
102 {
103     if(ql<=l && r<=qr) return Lv[x];
104     int mid=(l+r)>>1;
105     int ans=n+1;
106     if(ql<=mid) ans = min(ans, askL(l(x),l,mid,ql,qr));
107     if(mid<qr) ans = min(ans, askL(r(x),mid+1,r,ql,qr));
108     return ans;
109 }
110 
111 int askR(int x,int l,int r,int ql,int qr)
112 {
113     if(ql<=l && r<=qr) return Rv[x];
114     int mid=(l+r)>>1;
115     int ans=0;
116     if(ql<=mid) ans = max(ans, askR(l(x),l,mid,ql,qr));
117     if(mid<qr) ans = max(ans, askR(r(x),mid+1,r,ql,qr));
118     return ans;
119 }
120 
121 LL calc(int t,int l,int r)
122 {
123     if(l>r) return 0LL;
124     LL ans=0;
125     ans += (1LL<<t)*ask(1,1,n,l,r).sum%P;
126     return ans%P;
127 }
128 
129 bool cmp(int x,int y)
130 {
131     return a[x]>a[y];
132 }
133 
134 int main()
135 {
136     int T;
137     scanf("%d",&T);
138     while(T--)
139     {
140         scanf("%d",&n);
141         for(int i=1;i<=n;i++)
142         {
143             scanf("%d",&a[i]);
144             b[i]=i;
145         }
146         sort(b+1,b+n+1,cmp);
147         LL ans=0;
148         totn=0;
149         build(1,n);
150         for(int t=0;t<30;t++)
151         {
152             for(int i=1;i<=n;i++)
153             {
154                 if(a[i]&(1<<t)) c[i]=1;
155                 else c[i]=0;
156             }
157             totn=0;
158             build2(1,n);
159             totn=0;
160             build(1,n);
161             for(int i=1;i<=n;i++)
162             {
163                 int l=askR(1,1,n,1,b[i])+1;
164                 int r=askL(1,1,n,b[i],n)-1;
165                 ans += a[b[i]]*(calc(t,l,r)+P-calc(t,l,b[i]-1)+P-calc(t,b[i]+1,r))%P;
166                 add(1,1,n,b[i]);
167             }
168         }
169         cout << ans%P << endl;
170     }
171     return 0;
172 }
View Code

 

考虑优化此算法:

我们只要知道对于每个$x$,$L(x) \leq l \leq x$的从$x$开始的前缀$NimSum$为0,为1的前缀个数

与 $x \leq r \leq R(x)$ 的从$x$开始的后缀$NimSum$为0,为1的后缀个数。

这样,对于每一个$t$,$O(n)$预处理,单次查询$O(1)$即可。

总效率$O(nlogn)$,AC。

注意到会有一个区间有多个最大值的情况,这样,

$L(x)$要取到从$x$起向左第一个大于等于$a(x)$的数字右面,$R(x)$要取到从$x$起向右第一个大于$a(x)$的数字左面。

 

技术分享
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm> 
 5 
 6 #define N 100010
 7 #define LL long long
 8 #define P 1000000061LL
 9 
10 using namespace std;
11 
12 int n;
13 int a[N],L[N],R[N],c[N];
14 int suf[N][2],pre[N][2],S[N];
15 int q[N],en;
16 
17 int calc_pre(int l,int i)
18 {
19     int tmp=(S[i]-S[l-1])&1;
20     int ans = pre[i][1];
21     ans -= pre[l-1][tmp^1];
22     return ans;
23 }
24 
25 int calc_suf(int i,int r)
26 {
27     int tmp=(S[r]-S[i-1])&1;
28     int ans=suf[i][1];
29     ans -= suf[r+1][tmp^1];
30     return ans;
31 }
32 
33 int main()
34 {
35     int T;
36     scanf("%d",&T);
37     while(T--)
38     {
39         scanf("%d",&n);
40         for(int i=1;i<=n;i++) scanf("%d",&a[i]);
41         en=0;
42         for(int i=1;i<=n;i++)
43         {
44             while(en>0 && a[q[en]]<a[i]) en--;
45             if(!en) L[i]=1;
46             else L[i]=q[en]+1;
47             q[++en]=i;
48         }
49         en=0;
50         for(int i=n;i>=1;i--)
51         {
52             while(en>0 && a[q[en]]<=a[i]) en--;
53             if(!en) R[i]=n;
54             else R[i]=q[en]-1;
55             q[++en]=i;
56         }
57     //    for(int i=1;i<=n;i++) cout<<L[i]<<‘ ‘<<R[i]<<endl;
58         LL ans=0;
59         for(int t=0;t<31;t++)
60         {
61             pre[0][0]=pre[0][1]=0;
62             for(int i=1;i<=n;i++)
63             {
64                 c[i]=(a[i]>>t)&1;
65                 pre[i][0] = pre[i-1][c[i]] + (c[i]==0 ? 1:0);
66                 pre[i][1] = pre[i-1][c[i]^1] + (c[i]==0 ? 0:1);
67                 S[i]=S[i-1]+c[i];
68             }
69             suf[n+1][0]=suf[n+1][1]=0;
70             for(int i=n;i>=1;i--)
71             {
72                 suf[i][0] = suf[i+1][c[i]] + (c[i]==0 ? 1:0);
73                 suf[i][1] = suf[i+1][c[i]^1] + (c[i]==0 ? 0:1);
74             }
75             LL cntL[2],cntR[2];
76             for(int i=1;i<=n;i++)
77             {
78                 cntL[1] = calc_pre(L[i],i);
79                 cntL[0] = i-L[i]+1-cntL[1];
80                 cntR[1] = calc_suf(i,R[i]);
81                 cntR[0] = R[i]-i+1-cntR[1];
82                 ans += (1LL<<t)%P*a[i]%P*(cntL[0]*cntR[c[i]^1]%P + cntL[1]*cntR[c[i]]%P)%P;
83                 ans %= P;
84             }
85         }
86         cout << ans%P << endl;
87     }
88     return 0;
89 }
View Code

 

BZOJ4750 密码安全