【Luogu】P1393动态逆序对（树套树）
生活随笔
收集整理的這篇文章主要介紹了
【Luogu】P1393动态逆序对（树套树）
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
樹套樹。
每次刪掉x的時(shí)候會減去1到x-1里比x位置的數(shù)大的數(shù)和它構(gòu)成的逆序?qū)Γ约皒+1到n里比x位置的數(shù)小的數(shù)和它構(gòu)成的逆序?qū)Α?/p>
順帶一提我發(fā)現(xiàn)平衡樹insert的時(shí)候不是要splay一下嘛
如果改成每插入50個(gè)splay一下會快的飛起
我這道題就是這么卡過去的23333
放上代碼
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<algorithm>
#define mid ((l+r)>>1)
#define left (rt<<1)
#define right (rt<<1|1)
#define lson l,mid,left
#define rson mid+1,r,right
using namespace std;
int CNT; inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} int root[];
int q[]; struct Splay{
struct Node{
int size,sum,e[],val,fa;
}tree[];
int point,tot;
Splay(){ point=tot=; }
inline int iden(int x){ return x==tree[tree[x].fa].e[]; }
inline void connect(int x,int fa,int how){ tree[x].fa=fa; tree[fa].e[how]=x; }
inline void update(int x){
tree[x].size=tree[x].sum;
if(tree[x].e[]) tree[x].size+=tree[tree[x].e[]].size;
if(tree[x].e[]) tree[x].size+=tree[tree[x].e[]].size;
}
void rotate(int x,int rt){
int y=tree[x].fa; int r=tree[y].fa;
if(root[rt]==y) root[rt]=x;
int sony=iden(x),sonr=iden(y);
int b=tree[x].e[sony^];
connect(b,y,sony);
connect(y,x,sony^);
connect(x,r,sonr);
update(y);update(x);
}
void splay(int pos,int to,int rt){
to=tree[to].fa;
while(tree[pos].fa!=to){
if(tree[tree[pos].fa].fa==to) rotate(pos,rt);
else
if(iden(pos)==iden(tree[pos].fa)){ rotate(tree[pos].fa,rt); rotate(pos,rt); }
else{ rotate(pos,rt); rotate(pos,rt); }
}
}
int create(int val,int fa){
tree[++tot].val=val; tree[tot].sum=tree[tot].size=; tree[tot].fa=fa;
return tot;
}
int find(int val,int rt){
int now=root[rt];
while(){
if(!now) return ;
if(tree[now].val==val){
splay(now,root[rt],rt);
return now;
}
int nxt=val>tree[now].val?:;
if(!tree[now].e[nxt]) return ;
now=tree[now].e[nxt];
}
}
int build(int val,int rt){
point++;
if(!root[rt]){
root[rt]=create(val,);
return root[rt];
}
int now=root[rt];
while(){
tree[now].size++;
if(tree[now].val==val){
tree[now].sum++;
return now;
}
int nxt=val>tree[now].val?:;
if(!tree[now].e[nxt]){
int p=create(val,now);
connect(p,now,nxt);
return p;
}
now=tree[now].e[nxt];
}
}
void insert(int val,int rt){
int p=build(val,rt);
if((++CNT)%==){
splay(p,root[rt],rt);
CNT=;
}
}
void dele(int x){
tree[x].e[]=tree[x].e[]=;
if(x==tot) tot--;
}
void pop(int val,int rt){
int deal=find(val,rt);
if(!deal) return;
point--;
if(tree[deal].sum>){ tree[deal].sum--; tree[deal].size--; return;}
if(!tree[deal].e[]){
root[rt]=tree[deal].e[];
tree[root[rt]].fa=;
}
else{
int le=tree[deal].e[];
while(tree[le].e[]) le=tree[le].e[];
splay(le,tree[deal].e[],rt);
int ri=tree[deal].e[];
connect(ri,le,); tree[le].fa=;
root[rt]=le;
update(le);
}
dele(deal);
}
int rank(int val,int rt){
int ans=,now=root[rt];
while(){
if(!now) return ans;
if(tree[now].val==val){
ans+=tree[tree[now].e[]].size;
return ans;
}
if(val<tree[now].val) now=tree[now].e[];
else{
ans+=tree[tree[now].e[]].size+tree[now].sum;
now=tree[now].e[];
}
}
}
int arank(int val,int rt){
int ans=,now=root[rt];
while(){
if(!now) return ans;
if(tree[now].val==val){
ans+=tree[tree[now].e[]].size;
return ans;
}
if(val<tree[now].val){
ans+=tree[tree[now].e[]].size+tree[now].sum;
now=tree[now].e[];
}
else now=tree[now].e[];
}
}
int ask(int val,int rt,int opt){
if(opt==) return arank(val,rt);
else return rank(val,rt);
}
}s; void build(int l,int r,int rt){
for(int i=l;i<=r;++i) s.insert(q[i],rt);
if(l==r) return;
build(lson);
build(rson);
} int query(int from,int to,int val,int l,int r,int rt,int opt){
if(from>to) return ;
if(from<=l&&to>=r) return s.ask(val,rt,opt);
int cnt=;
if(from<=mid) cnt+=query(from,to,val,lson,opt);
if(to>mid) cnt+=query(from,to,val,rson,opt);
return cnt;
} void Delete(int o,int val,int l,int r,int rt){
s.pop(val,rt);
if(l==r) return;
if(o<=mid) Delete(o,val,lson);
else Delete(o,val,rson);
} int ans; int main(){
int n=read(),m=read();
for(int i=;i<=n;++i) q[i]=read();
build(,n,);
for(int i=;i<=n;++i) ans+=query(,i-,q[i],,n,,);
printf("%d",ans);
for(int i=;i<=m;++i){
int pos=read();
ans-=query(,pos-,q[pos],,n,,);
ans-=query(pos+,n,q[pos],,n,,);
printf(" %d",ans);
Delete(pos,q[pos],,n,);
}
return ;
}
總結(jié)
以上是生活随笔為你收集整理的【Luogu】P1393动态逆序对（树套树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 已拦截跨源请求：同源策略禁止读取位于 h
- 下一篇： C++ NRV优化