网站建设前期准备方案,网络卖东西的平台有哪些,建设部网站公示公告,下载app白白的#xff08;baibaide#xff09; 有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$#xff0c;一开始每个位置都是白色。如果一个区间中每个位置都是白色#xff0c;则称这是一个白白的区间。如果一个白白的区间向左或向右延长后都不是白白的区间了#xff0c;则称这…白白的baibaide 有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$一开始每个位置都是白色。如果一个区间中每个位置都是白色则称这是一个白白的区间。如果一个白白的区间向左或向右延长后都不是白白的区间了则称这是一个极长的白白的区间。有 $q$ 次操作每次操作会修改某个位置的值或者把某个位置变成黑色。每次操作后求所有极长的白白的区间中含有的逆序对数的异或和。强制在线。 $n ≤ 150000q ≤ 200000 ≤ a_i ≤ 10^91 ≤ x ≤ n0 ≤ y ≤ 10^9$ $Subtask1(10pts) : n ≤ 10^3, q ≤ 10^3$ $Subtask2(20pts) : 只有 0 操作$ $Subtask3(30pts) : 只有 1 操作$ $Subtask4(40pts) : 没有特殊限制$ Solution 毒题 有种高级的东西叫做启发式分裂可以应用于只分裂不合并的题目。 每次扫描较小的那一段复杂度似乎是nlogn的。 那我们考虑每次枚举小的那一段区间的每个数x然后在大的区间中查找比x大小的数的个数也就是x对于大区间的逆序对贡献。 大区间的答案等于原来区间的答案减去每次查出的答案小的重新算。 统计小于主席树就行。修改树套树。 然而这题没完... 我们算下复杂度:分裂$nlogn$ 树套树 $nlog^2n$ 修改 $qlog^2n$ 总复杂度 $ nlog^3n qlog^2n $ n150000 炸了 我们考虑优化前面的那个^3 按权值为比较大小的关键字建splay 一棵splay维护一段区间分裂时查询某一段比x大的有几个。 分裂完小的区间暴力重建splay总共可以有多棵splay 这样前面就是$nlog^2n$了 树套树似乎不用了然而splay在单点修改时不能维护答案于是还要。 总复杂度 $ nlog^2n qlog^2n $ 颠覆我对数据结构的认知 1 #includecstdio2 #includeiostream3 #includecstdlib4 #includecstring5 #includealgorithm6 #includecmath7 #includeset8 #define ll long long9 #define maxn 15000510 #define Max 100000000011 using namespace std;12 int n,q,a[maxn],rt[maxn],tot,cnt,root[maxn];13 ll Ans,ans[maxn];14 struct no{15 int ls,rs,v;16 }tr[maxn*400];17 setintdd;18 void wh(int k){19 tr[k].vtr[tr[k].ls].vtr[tr[k].rs].v;20 }21 void add(int k,int l,int r,int pl,int v){22 if(!k)kcnt;23 if(lr){24 tr[k].vv;25 return;26 }27 int midlr1;28 if(plmid)add(tr[k].ls,l,mid,pl,v);29 else add(tr[k].rs,mid1,r,pl,v);30 wh(k);31 }32 ll t_ask(int k,int l,int r,int v,int fl){33 if(!k)return 0;34 ll sl0,sr0;35 if(lr){36 return tr[k].v;37 }38 int midlr1;39 if(fl1){//v40 if(vmid)return tr[tr[k].rs].vt_ask(tr[k].ls,l,mid,v,fl);41 else return t_ask(tr[k].rs,mid1,r,v,fl);42 }43 else{44 if(vmid)return t_ask(tr[k].ls,l,mid,v,fl);45 else return tr[tr[k].ls].vt_ask(tr[k].rs,mid1,r,v,fl);46 }47 }48 ll ask(int l,int r,int v,int fl){49 if(lr)return 0;50 ll sl0,sr0;51 if(fl)v;else v--;52 if(l-10)for(int il-1;i;i-i-i)slt_ask(root[i],0,Max,v,fl);53 for(int ir;i;i-i-i)srt_ask(root[i],0,Max,v,fl);54 return sr-sl;55 }56 ll query(int l,int r,int x){57 ll n10,n20;58 n1ask(l,x-1,a[x],1);n2ask(x1,r,a[x],0);59 return n1n2;60 }61 struct Splay{62 int ch[2],f,v,num,sz;63 }t[maxn*50];64 void upd(int x){65 int lst[x].ch[0],rst[x].ch[1];66 t[x].szt[ls].szt[rs].szt[x].num;67 }68 int get(int x){return t[t[x].f].ch[1]x;}69 void rotate(int x){70 int yt[x].f,zt[y].f;71 int wxget(x),wyget(y);72 t[z].ch[wy]x;t[x].fz;73 t[y].ch[wx]t[x].ch[wx^1];t[t[x].ch[wx^1]].fy;74 t[x].ch[wx^1]y;t[y].fx;75 upd(y);upd(x);76 }77 void splay(int x,int g){78 while(t[x].f!g){79 int yt[x].f,zt[y].f;80 if(z!g)rotate(get(x)get(y)?y:x);81 rotate(x);82 }83 }84 void modify(int R,int k,int x,int Num){85 int fa0;86 while(kt[k].v!x){87 fak,kt[k].ch[xt[k].v];88 }89 if(k)t[k].numNum;90 else {91 ktot;92 if(fa)t[fa].ch[xt[fa].v]k;93 t[k].vx;t[k].numt[k].sz1;t[k].ffa;94 }95 splay(k,0);Rk;96 }97 ll ask_min(int k,int v){98 ll sum0;99 while(k){
100 if(t[k].vv)sumt[t[k].ch[0]].szt[k].num,kt[k].ch[1];
101 else if(t[k].vv){
102 sumt[t[k].ch[0]].sz;
103 break;
104 }
105 else kt[k].ch[0];
106 }
107 return sum;
108 }
109 ll ask_max(int k,int v){//
110 ll sum0;
111 while(k){
112 if(t[k].vv)kt[k].ch[1];
113 else if(t[k].vv){
114 sumt[t[k].ch[1]].sz;
115 break;
116 }
117 else sumt[t[k].ch[1]].szt[k].num,kt[k].ch[0];
118 }
119 return sum;
120 }
121 int main()
122 {
123 cinnq;dd.insert(1);dd.insert(n1);
124 for(int i1;in;i){
125 scanf(%d,a[i]);
126 modify(rt[1],rt[1],a[i],1);
127 }
128 for(int i1;in;i)
129 for(int ji;jn;jj-j){
130 add(root[j],0,Max,a[i],1);
131 }
132 for(int i1;in;i)ans[1]query(1,n,i);
133 ans[1]/2;Ansans[1];ll la0;
134 for(int i1,op;iq;i){
135 scanf(%d,op);
136 ll x,y;
137 if(op0){
138 scanf(%lld%lld,x,y);x^la;y^la;
139 setint::iterator it;
140 itdd.upper_bound(x);
141 int r*it-1;it--;int l*it;
142 Ans^ans[l];
143 ll numquery(l,r,x);
144 modify(rt[l],rt[l],a[x],-1);
145 ans[l]-num;
146 for(int jx;jn;jj-j)add(root[j],0,Max,a[x],-1);
147 a[x]y;
148 modify(rt[l],rt[l],a[x],1);
149 for(int jx;jn;jj-j)add(root[j],0,Max,a[x],1);
150 numquery(l,r,x);
151 ans[l]num;Ans^ans[l];
152 printf(%lld\n,Ans);laAns;
153 }
154 else {
155 scanf(%lld,x);x^la;
156 setint::iterator it;
157 itdd.upper_bound(x);
158 int r*it-1;it--;int l*it;
159 Ans^ans[l];ll co0;
160 if(xl){
161 coask_min(rt[l],a[l]);
162 modify(rt[l],rt[l],a[l],-1);
163 ans[l1]ans[l]-co;ans[l]0;
164 rt[l1]rt[l];rt[l]0;
165 Ans^ans[l1];
166 dd.insert(l1);
167 }
168 else if(xr){
169 coask_max(rt[l],a[r]);
170 modify(rt[l],rt[l],a[r],-1);
171 ans[l]-co;Ans^ans[l];
172 dd.insert(r);
173 }
174 else {
175 if(x-lr-x){
176 for(int il;ix;i){
177 coask_min(rt[l],a[i]);
178 modify(rt[l],rt[l],a[i],-1);
179 }
180 ans[x1]ans[l]-co;
181 rt[x1]rt[l];rt[l]0;ans[l]0;
182 for(int il;ix;i){
183 modify(rt[l],rt[l],a[i],1);
184 ans[l]ask_max(rt[l],a[i]);
185 }
186 Ans(Ans^ans[l]^ans[x1]);
187 }
188 else {
189 for(int ir;ix;i--){
190 coask_max(rt[l],a[i]);
191 modify(rt[l],rt[l],a[i],-1);
192 }
193 ans[l]-co;
194 for(int ix1;ir;i){
195 modify(rt[x1],rt[x1],a[i],1);
196 ans[x1]ask_max(rt[x1],a[i]);
197 }
198 Ans(Ans^ans[l]^ans[x1]);
199 }
200 dd.insert(x);dd.insert(x1);
201 }
202 printf(%lld\n,Ans);laAns;
203 }
204 }
205 return 0;
206 } View Code 转载于:https://www.cnblogs.com/liankewei/p/10657581.html
