白白的（baibaide）

白白的（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*400];
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>>1;
    if(pl<=mid)add(tr[k].ls,l,mid,pl,v);
    else add(tr[k].rs,mid+1,r,pl,v);
    wh(k);
}
ll t_ask(int k,int l,int r,int v,int fl){
    if(!k)return 0;
    ll sl=0,sr=0;
    if(l==r){
        return tr[k].v;
    }
    int mid=l+r>>1;
    if(fl==1){//>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+1,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+1,r,v,fl);
    }
}
ll ask(int l,int r,int v,int fl){
    if(l>r)return 0;
    ll sl=0,sr=0;
    if(fl)v++;else v--;
    if(l-1>0)for(int i=l-1;i;i-=i&-i)sl+=t_ask(root[i],0,Max,v,fl);
    for(int i=r;i;i-=i&-i)sr+=t_ask(root[i],0,Max,v,fl);
    return sr-sl;
}
ll query(int l,int r,int x){
    ll n1=0,n2=0;
    n1=ask(l,x-1,a[x],1);n2=ask(x+1,r,a[x],0);
    return n1+n2;
}
struct Splay{
    int ch[2],f,v,num,sz;
}t[maxn*50];
void upd(int x){
    int ls=t[x].ch[0],rs=t[x].ch[1];
    t[x].sz=t[ls].sz+t[rs].sz+t[x].num;
}
int get(int x){return t[t[x].f].ch[1]==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^1];t[t[x].ch[wx^1]].f=y;
    t[x].ch[wx^1]=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=0;
    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=1;t[k].f=fa;
    }
    splay(k,0);R=k;
}
ll ask_min(int k,int v){
    ll sum=0;
    while(k){
        if(t[k].v<v)sum+=t[t[k].ch[0]].sz+t[k].num,k=t[k].ch[1];
        else if(t[k].v==v){
            sum+=t[t[k].ch[0]].sz;
            break;
        }    
        else k=t[k].ch[0];
    }
    return sum;
}
ll ask_max(int k,int v){//>
    ll sum=0;
    while(k){
        if(t[k].v<v)k=t[k].ch[1];
        else if(t[k].v==v){
            sum+=t[t[k].ch[1]].sz;
            break;
        }    
        else sum+=t[t[k].ch[1]].sz+t[k].num,k=t[k].ch[0];
    }
    return sum;
}
int main()
{
    cin>>n>>q;dd.insert(1);dd.insert(n+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        modify(rt[1],rt[1],a[i],1);
    }
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j+=j&-j){
        add(root[j],0,Max,a[i],1);
    }
    for(int i=1;i<=n;i++)ans[1]+=query(1,n,i);
    ans[1]/=2;Ans=ans[1];ll la=0;
    for(int i=1,op;i<=q;i++){
        scanf("%d",&op);
        ll x,y;
        if(op==0){
            scanf("%lld%lld",&x,&y);x^=la;y^=la;
            set<int>::iterator it;
            it=dd.upper_bound(x);
            int r=*it-1;it--;int l=*it;
            Ans^=ans[l];
            ll num=query(l,r,x);
            modify(rt[l],rt[l],a[x],-1);
            ans[l]-=num;
            for(int j=x;j<=n;j+=j&-j)add(root[j],0,Max,a[x],-1);
            a[x]=y;
            modify(rt[l],rt[l],a[x],1);
            for(int j=x;j<=n;j+=j&-j)add(root[j],0,Max,a[x],1);
            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-1;it--;int l=*it;
            Ans^=ans[l];ll co=0;
            if(x==l){
                co=ask_min(rt[l],a[l]);
                modify(rt[l],rt[l],a[l],-1);
                ans[l+1]=ans[l]-co;ans[l]=0;
                rt[l+1]=rt[l];rt[l]=0;
                Ans^=ans[l+1];
                dd.insert(l+1);
            }
            else if(x==r){
                co=ask_max(rt[l],a[r]);
                modify(rt[l],rt[l],a[r],-1);
                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],-1);
                    }
                    ans[x+1]=ans[l]-co;
                    rt[x+1]=rt[l];rt[l]=0;ans[l]=0;
                    for(int i=l;i<x;i++){
                        modify(rt[l],rt[l],a[i],1);
                        ans[l]+=ask_max(rt[l],a[i]);
                    }
                    Ans=(Ans^ans[l]^ans[x+1]);
                }
                else {
                    for(int i=r;i>=x;i--){
                        co+=ask_max(rt[l],a[i]);
                        modify(rt[l],rt[l],a[i],-1);
                    }
                    ans[l]-=co;
                    for(int i=x+1;i<=r;i++){
                        modify(rt[x+1],rt[x+1],a[i],1);
                        ans[x+1]+=ask_max(rt[x+1],a[i]);
                    }
                    Ans=(Ans^ans[l]^ans[x+1]);
                }
                dd.insert(x);dd.insert(x+1);
            }
            printf("%lld\n",Ans);la=Ans;
        }
    }
    return 0;
}

?