白白的（baibaide）
2024-08-28 12:41:56
白白的（baibaide）
有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，一开始每个位置都是白色。如果一个区间中每个位置都是白色，则称这是一个白白的区间。如果一个白白的区间向左或向右延长后都不是白白的区间了，则称这是一个极长的白白的区间。有 $q$ 次操作，每次操作会修改某个位置的值，或者把某个位置变成黑色。每次操作后，求所有极长的白白的区间中含有的逆序对数的异或和。强制在线。
$n ≤ 150000，q ≤ 20000，0 ≤ a_i ≤ 10^9，1 ≤ x ≤ n，0 ≤ 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 $
n=150000 炸了
我们考虑优化前面的那个^3
按权值为比较大小的关键字建splay
一棵splay维护一段区间，分裂时查询某一段比x大的有几个。
分裂完小的区间暴力重建splay，总共可以有多棵splay
这样前面就是$nlog^2n$了
树套树似乎不用了？然而splay在单点修改时不能维护答案，于是还要。
总复杂度 $ nlog^2n + qlog^2n $
颠覆我对数据结构的认知
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
#define ll long long
#define maxn 150005
#define Max 1000000000
using namespace std;
int n,q,a[maxn],rt[maxn],tot,cnt,root[maxn];
ll Ans,ans[maxn];
struct no{
int ls,rs,v;
}tr[maxn*];
set<int>dd;
void wh(int k){
tr[k].v=tr[tr[k].ls].v+tr[tr[k].rs].v;
}
void add(int &k,int l,int r,int pl,int v){
if(!k)k=++cnt;
if(l==r){
tr[k].v+=v;
return;
}
int mid=l+r>>;
if(pl<=mid)add(tr[k].ls,l,mid,pl,v);
else add(tr[k].rs,mid+,r,pl,v);
wh(k);
}
ll t_ask(int k,int l,int r,int v,int fl){
if(!k)return ;
ll sl=,sr=;
if(l==r){
return tr[k].v;
}
int mid=l+r>>;
if(fl==){//>v
if(v<=mid)return tr[tr[k].rs].v+t_ask(tr[k].ls,l,mid,v,fl);
else return t_ask(tr[k].rs,mid+,r,v,fl);
}
else{
if(v<=mid)return t_ask(tr[k].ls,l,mid,v,fl);
else return tr[tr[k].ls].v+t_ask(tr[k].rs,mid+,r,v,fl);
}
}
ll ask(int l,int r,int v,int fl){
if(l>r)return ;
ll sl=,sr=;
if(fl)v++;else v--;
if(l->)for(int i=l-;i;i-=i&-i)sl+=t_ask(root[i],,Max,v,fl);
for(int i=r;i;i-=i&-i)sr+=t_ask(root[i],,Max,v,fl);
return sr-sl;
}
ll query(int l,int r,int x){
ll n1=,n2=;
n1=ask(l,x-,a[x],);n2=ask(x+,r,a[x],);
return n1+n2;
}
struct Splay{
int ch[],f,v,num,sz;
}t[maxn*];
void upd(int x){
int ls=t[x].ch[],rs=t[x].ch[];
t[x].sz=t[ls].sz+t[rs].sz+t[x].num;
}
int get(int x){return t[t[x].f].ch[]==x;}
void rotate(int x){
int y=t[x].f,z=t[y].f;
int wx=get(x),wy=get(y);
t[z].ch[wy]=x;t[x].f=z;
t[y].ch[wx]=t[x].ch[wx^];t[t[x].ch[wx^]].f=y;
t[x].ch[wx^]=y;t[y].f=x;
upd(y);upd(x);
}
void splay(int x,int g){
while(t[x].f!=g){
int y=t[x].f,z=t[y].f;
if(z!=g)rotate(get(x)==get(y)?y:x);
rotate(x);
}
}
void modify(int &R,int k,int x,int Num){
int fa=;
while(k&&t[k].v!=x){
fa=k,k=t[k].ch[x>t[k].v];
}
if(k)t[k].num+=Num;
else {
k=++tot;
if(fa)t[fa].ch[x>t[fa].v]=k;
t[k].v=x;t[k].num=t[k].sz=;t[k].f=fa;
}
splay(k,);R=k;
}
ll ask_min(int k,int v){
ll sum=;
while(k){
if(t[k].v<v)sum+=t[t[k].ch[]].sz+t[k].num,k=t[k].ch[];
else if(t[k].v==v){
sum+=t[t[k].ch[]].sz;
break;
}
else k=t[k].ch[];
}
return sum;
}
ll ask_max(int k,int v){//>
ll sum=;
while(k){
if(t[k].v<v)k=t[k].ch[];
else if(t[k].v==v){
sum+=t[t[k].ch[]].sz;
break;
}
else sum+=t[t[k].ch[]].sz+t[k].num,k=t[k].ch[];
}
return sum;
}
int main()
{
cin>>n>>q;dd.insert();dd.insert(n+);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
modify(rt[],rt[],a[i],);
}
for(int i=;i<=n;i++)
for(int j=i;j<=n;j+=j&-j){
add(root[j],,Max,a[i],);
}
for(int i=;i<=n;i++)ans[]+=query(,n,i);
ans[]/=;Ans=ans[];ll la=;
for(int i=,op;i<=q;i++){
scanf("%d",&op);
ll x,y;
if(op==){
scanf("%lld%lld",&x,&y);x^=la;y^=la;
set<int>::iterator it;
it=dd.upper_bound(x);
int r=*it-;it--;int l=*it;
Ans^=ans[l];
ll num=query(l,r,x);
modify(rt[l],rt[l],a[x],-);
ans[l]-=num;
for(int j=x;j<=n;j+=j&-j)add(root[j],,Max,a[x],-);
a[x]=y;
modify(rt[l],rt[l],a[x],);
for(int j=x;j<=n;j+=j&-j)add(root[j],,Max,a[x],);
num=query(l,r,x);
ans[l]+=num;Ans^=ans[l];
printf("%lld\n",Ans);la=Ans;
}
else {
scanf("%lld",&x);x^=la;
set<int>::iterator it;
it=dd.upper_bound(x);
int r=*it-;it--;int l=*it;
Ans^=ans[l];ll co=;
if(x==l){
co=ask_min(rt[l],a[l]);
modify(rt[l],rt[l],a[l],-);
ans[l+]=ans[l]-co;ans[l]=;
rt[l+]=rt[l];rt[l]=;
Ans^=ans[l+];
dd.insert(l+);
}
else if(x==r){
co=ask_max(rt[l],a[r]);
modify(rt[l],rt[l],a[r],-);
ans[l]-=co;Ans^=ans[l];
dd.insert(r);
}
else {
if(x-l<r-x){
for(int i=l;i<=x;i++){
co+=ask_min(rt[l],a[i]);
modify(rt[l],rt[l],a[i],-);
}
ans[x+]=ans[l]-co;
rt[x+]=rt[l];rt[l]=;ans[l]=;
for(int i=l;i<x;i++){
modify(rt[l],rt[l],a[i],);
ans[l]+=ask_max(rt[l],a[i]);
}
Ans=(Ans^ans[l]^ans[x+]);
}
else {
for(int i=r;i>=x;i--){
co+=ask_max(rt[l],a[i]);
modify(rt[l],rt[l],a[i],-);
}
ans[l]-=co;
for(int i=x+;i<=r;i++){
modify(rt[x+],rt[x+],a[i],);
ans[x+]+=ask_max(rt[x+],a[i]);
}
Ans=(Ans^ans[l]^ans[x+]);
}
dd.insert(x);dd.insert(x+);
}
printf("%lld\n",Ans);la=Ans;
}
}
return ;
}
最新文章
- HA 高可用软件系统保养指南
- java spring 邮件发送
- c++防止客户端多开巧妙代码
- js常用功能汇总
- IOS 项目 小说 1
- navicat 的查询功能
- 关于VOID *在cl与gcc的不同(无意中发现)
- BZOJ3238 [Ahoi2013]差异
- reds pub/sub官方文档翻译
- Libvirt 虚拟化库剖析
- Android源码是这样搞到的(图解)
- Oracle merge into 使用记录
- HDOJ 3622 - Bomb Game 2-sat+二分....细心...
- [AngularJS] Transforming raw JSON data to meaningful output in AngularJS
- C++中string类的使用方法
- mongodb命令行基础语法
- 影响 POST 请求文件上传失败的几个环节的配置（php + nginx）
- python五十七课——正则表达式（多个字符）
- BZOJ.4542.[HNOI2016]大数(莫队)
- HDU 2276 Kiki & Little Kiki 2 矩阵构造