关于强制在线单点修改询问区间逆序对数单根号双log复杂度的求解方法以及拓展
空気浮遊
2019年02月25日
考场上 + 事后调写出来了但发现没什么用，因为一开始以为是单根号单 log 的求解，结果最后才发现是双 log，然后 gg。
写都写了还是保存一下吧。
Solution
分块处理。
预处理每个块之间左对右的逆序对数贡献，这里复杂度是 $O(n\log \sqrt{n} + n\sqrt{n})$。
预处理每个块内单独的逆序对数贡献，这里复杂度是 $O(n\log \sqrt{n})$。
询问的时候分三个部分 ABC，A 和 C 是多出来的块，B 是整块。
那么就变成了计算 A 对 B 的贡献，B 对 C 的贡献，A 对 C 的贡献，和 ABC 独自的贡献。
A 和 C 独自的贡献可以复杂度 $O(\sqrt{n} \log \sqrt{n})$ 做出来。
B 的贡献预处理出来，动态二维前缀和用二维线段树维护。
A 对 B 的贡献可以枚举 A 然后在 B 里用树套树询问出来，这里要单根号 + 两个 $\log$。
A 对 C 的贡献可以 $O(\sqrt{n} + \sqrt{n} \log \sqrt{n})$ 做出来。
修改的时候考虑块与块之间的变动，这里可以用 $O(n\log \sqrt{n} \log 1e9)$ 做出来。
考虑块单独的变动，这里还是 $O(\sqrt{n} \log \sqrt{n})$。
剩下的小量就不讨论了。
使用价值：无。可以拿来出毒瘤提答题。
代码复杂度：二维线段树 + 树状数组套主席树 + 分块，至少考场上不是很好调。
如果有人能优化到单 $\log$ 或者有这样的解法请跟我说一声。
一些拓展
http://olddrivertree.blog.uoj.ac/blog/4656
去查了下相关资料是由 lxl 提出的不带修强制在线的优秀做法的，严格 $O(q\sqrt{n})$。
简单来讲就是预处理 $f_{i,j}$ 为前 $i$ 个数对第 $j$ 个块的贡献，这个可以先对每个块排序之后块两两之间做归并然后前缀和求出。
同理也可以预处理第 $i$ 个块对后 $j$ 个数的贡献。
然后可以一开始排序。单块的询问可以一开始预处理好（同时将块排序之后就可以直接线性排序，就是在当前询问区间的数顺序取出），然后每次散块的询问就可以线性排序归并来求了。这个就是很严格的 $O(n\sqrt{n}+n\log{n})$ 复杂度了。
那么如果加入单点修改，实际影响到的东西就是 $f_{i,j}$ 和每个块的排序。
那么单点修改，单个块的排序（顺便计算一下单个块的贡献）是 $O(\sqrt{n}\log \sqrt{n})$，而对于被更改的第 $i$ 个点对第 $j$ 个块的贡献，首先可以在块内二分出单点对块的贡献变成了什么，然后用个树状数组维护一下，也就是 $O(\sqrt{n}\log \sqrt{n})$。这样子的话就可以做到优秀的常数的单根号单 $\log$ 复杂度的求解了...？
然而并不是，我假了。因为你可以很轻易的算出你对其它块的影响变化却很难算出其它点对你块的影响变化。
我还是 naive 了哈哈哈
Code
代码还加了一点其它东西。正确性是能保证的。常数很大。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cassert>
using namespace std;
template<typename T> inline void gn(T &x) {
char ch=getchar(); x=0;
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
const int N=4e5+10, M=390, V=1e9;
int arr[N], bl[M], br[M], pos[N];
int arr2[N];
int val[M][M], aval[M];
char col[N];
typedef long long ll;
int cac(int l1, int r1, int l2, int r2) {
int a[M], b[M], x=r1-l1+1, y=r2-l2+1;
copy(arr+l1, arr+r1+1, a);
copy(arr+l2, arr+r2+1, b);
sort(a, a+x), sort(b, b+y);
int i=0, j=0, ret=0;
while(i<x && j<y) {
if(a[i]>b[j]) ret+=x-i, j++;
else i++;
}
return ret;
} // caculate segment [l1, r1] and [l2, r2]
int cac2(int x, int y) {
int l1=bl[x], r1=br[x], l2=bl[y], r2=br[y];
int i=l1, j=l2, ret=0;
while(i<=r1 && j<=r2) {
if(arr2[i]>arr2[j]) ret+=r1+1-i, j++;
else i++;
}
return ret;
}
int x;
#define ls x<<1
#define rs x<<1|1
int n, q, size, m;
namespace S1 {
struct Segtree {
ll su[M<<2];
Segtree() { memset(su, 0, sizeof(su)); }
void build(int x, int l, int r, int dx) {
if(l==r) { su[x]=val[dx][r]; return; }
int mid=(l+r)>>1; build(ls, l, mid, dx), build(rs, mid+1, r, dx);
su[x]=su[ls]+su[rs];
}
void updata(int x, int l, int r, int d, int v) {
if(l==r) { su[x]+=v; return; }
int mid=(l+r)>>1;
if(d<=mid) updata(ls, l, mid, d, v);
else updata(rs, mid+1, r, d, v);
su[x]=su[ls]+su[rs];
}
ll query(int x, int l, int r, int xl, int xr) {
if(xl<=l && r<=xr) return su[x];
int mid=(l+r)>>1; ll ret=0;
if(xl<=mid) ret+=query(ls, l, mid, xl, xr);
if(xr>mid) ret+=query(rs, mid+1, r, xl, xr);
return ret;
}
void pup (const Segtree &x, const Segtree &y) {
for(int i=0;i<(M<<2);i++) su[i]=x.su[i]+y.su[i];
}
} ;
Segtree seg[M<<2];
void build(int x, int l, int r) {
if(l==r) { seg[x].build(1, 1, m, l); return; }
int mid=(l+r)>>1; build(ls, l, mid), build(rs, mid+1, r);
seg[x].pup(seg[ls],seg[rs]);
}
void updata(int x, int l, int r, int dx, int dy, int v) {
seg[x].updata(1, 1, m, dy, v);
if(l==r) return;
int mid=(l+r)>>1;
if(dx<=mid) updata(ls, l, mid, dx, dy, v);
else updata(rs, mid+1, r, dx, dy, v);
}
ll query(int x, int l, int r, int xl, int xr, int yl, int yr) {
if(xl<=l && r<=xr) return seg[x].query(1, 1, m, yl, yr);
int mid=(l+r)>>1; ll ret=0;
if(xl<=mid) ret+=query(ls, l, mid, xl, xr, yl, yr);
if(xr>mid) ret+=query(rs, mid+1, r, xl, xr, yl, yr);
return ret;
}
}
namespace S2 {
struct Data {
int l, r;
Data(int l=0, int r=0):l(l), r(r) {}
} v[N<<2], t[N<<2];
void pud(int x) {
if(!t[x].l) return;
t[ls]=t[rs]=v[ls]=v[rs]=t[x], t[x].l=0;
}
void updata(int x, int l, int r, int xl, int xr) {
pud(x);
if(xl<=l && r<=xr) { t[x]=v[x]=Data(xl, xr); return; }
int mid=(l+r)>>1;
if(xl<=mid) updata(ls, l, mid, xl, xr);
if(xr>mid) updata(rs, mid+1, r, xl, xr);
}
Data query (int x, int l, int r, int d) {
pud(x);
if(l==r) return v[x];
int mid=(l+r)>>1;
if(d<=mid) return query(ls, l, mid, d);
else return query(rs, mid+1, r, d);
}
} // caucalte color
#undef ls
#undef rs
namespace S3 {
struct Node *nil;
struct Node {
Node *ls=nil, *rs=nil;
int v=0;
} *C[M];
void ini() { nil=new Node(); nil->ls=nil->rs=nil, fill(C, C+M, nil); }
#define lowbit(x) x&-x
void updata(Node *&x, int l, int r, int d, int v) {
if(x==nil) x=new Node();
x->v+=v;
if(l==r) return;
int mid=(l+r)>>1;
if(d<=mid) updata(x->ls, l, mid, d, v);
else updata(x->rs, mid+1, r, d, v);
}
ll query(Node *&x, int l, int r, int xl, int xr) {
if(xl<=l && r<=xr) return x->v;
int mid=(l+r)>>1; ll ret=0;
if(xl<=mid) ret+=query(x->ls, l, mid, xl, xr);
if(xr>mid) ret+=query(x->rs, mid+1, r, xl, xr);
return ret;
}
void updata(int x, int y, int w) {
while(x<M) updata(C[x], 0, V, y, w), x+=lowbit(x);
}
ll query(int x, int l, int r) {
if(l>r) return 0;
ll ret=0;
while(x) {
ret+=query(C[x], 0, V, l, r);
x-=lowbit(x);
}
return ret;
}
}
int sa[N], scac[N];
void mergesort(int l, int r, int &tot) {
if(l==r) return;
int mid=(l+r)>>1; mergesort(l, mid, tot), mergesort(mid+1, r, tot);
int i=l, j=mid+1, k=l;
while(i<=mid && j<=r) {
if(sa[i]>sa[j]) tot+=mid-i+1, scac[k++]=sa[j++];
else scac[k++]=sa[i++];
}
while(i<=mid) scac[k++]=sa[i++];
while(j<=r) scac[k++]=sa[j++];
copy(scac+l, scac+r+1, sa+l);
}
int cac(int l, int r) {
copy(arr+l, arr+r+1, sa+1);
int ret=0;
mergesort(1, r-l+1, ret);
return ret;
}
ll tcac(int l, int r) {
int xl=pos[l]+1, xr=pos[r]-1;
ll ret=cac(l, min(br[pos[l]], r)); // indie
if(xl<=xr)
for(int i=l; i<=min(br[pos[l]], r); i++)
if(arr[i])
ret+=S3::query(xr, 0, arr[i]-1)-S3::query(xl-1, 0, arr[i]-1); // l -> mid
if(pos[r]!=pos[l]) {
ret+=cac(bl[pos[r]], r)+cac(l, br[pos[l]], bl[pos[r]], r); // indie & l->R
if(xl<=xr)
for(int i=bl[pos[r]]; i<=r; i++)
if(arr[i]<V) ret+=S3::query(xr, arr[i]+1, V)-S3::query(xl-1, arr[i]+1, V); // mid -> r
}
if(xl<=xr) ret+=S1::query(1, 1, m, xl, xr, xl, xr); // mid -> mid & indie
return ret;
}
ll rans; // the answer
void modify(int x, int y) {
if(col[x]) return;
S2::Data bel=S2::query(1, 1, n, x);
rans^=tcac(bel.l, bel.r);
int np=pos[x];
for(int i=1;i<np;i++)
val[i][np]=-S3::query(i, arr[x]+1, V)+S3::query(i-1, arr[x]+1, V);
for(int i=np+1;i<=m;i++)
val[np][i]=-S3::query(i, 0, arr[x]-1)+S3::query(i-1, 0, arr[x]-1);
S3::updata(np, arr[x], -1);
arr[x]=y;
ll ne=cac(bl[np], br[np]);
S1::updata(1, 1, m, np, np, ne-val[np][np]), val[np][np]=ne;
S3::updata(np, arr[x], 1);
for(int i=1;i<np;i++) {
val[i][np]+=S3::query(i, arr[x]+1, V)-S3::query(i-1, arr[x]+1, V);
S1::updata(1, 1, m, i, np, val[i][np]);
}
for(int i=np+1;i<=m;i++) {
val[np][i]+=S3::query(i, 0, arr[x]-1)-S3::query(i-1, 0, arr[x]-1);
S1::updata(1, 1, m, np, i, val[np][i]);
}
rans^=tcac(bel.l, bel.r);
}
void paintb(int x) {
S2::Data bel=S2::query(1, 1, n, x);
col[x]=1;
rans^=tcac(bel.l, bel.r);
if(!col[x-1] && x>1) {
S2::updata(1, 1, n, bel.l, x-1);
rans^=tcac(bel.l, x-1);
}
if(!col[x+1] && x<n) {
S2::updata(1, 1, n, x+1, bel.r);
rans^=tcac(x+1, bel.r);
}
}
int main() {
#ifndef LOCAL
freopen("baibaide.in","r",stdin);
freopen("baibaide.out","w",stdout);
#endif
#ifdef LOCAL
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
S3::ini();
gn(n), gn(q);
size=sqrt(n), m=(n-1)/size+1;
for(int i=1;i<=n;i++) gn(arr[i]), arr2[i]=arr[i], pos[i]=(i-1)/size+1;
for(int i=1;i<=m;i++) bl[i]=br[i-1]+1, br[i]=i*size;
br[m]=n;
for(int i=1;i<=m;i++) val[i][i]=cac(bl[i], br[i]), sort(arr2+bl[i], arr2+br[i]+1);
for(int i=1;i<=m;i++)
for(int j=i+1;j<=m;j++)
val[i][j]=cac2(i, j);
S1::build(1, 1, m);
for(int i=1;i<=n;i++) S3::updata(pos[i], arr[i], 1);
S2::updata(1, 1, n, 1, n);
rans=tcac(1, n);
ll lst=0;
int opt; ll x, y;
cerr<<"PRE"<<endl;
while(q--) {
gn(opt), gn(x), x^=lst;
if(!opt) gn(y), y^=lst, modify(x, y);
else paintb(x);
printf("%lld\n", lst=rans);
}
cerr<<"FINISHED"<<endl;
return 0;
}