[COCI2010-2011#7] UPIT

约定:视$n,q$同阶

看一下题目的操作

1.区间赋值

2.区间差分加

3.插入元素

4.区间查询

我们知道1,2操作都是可以用懒标记维护的，具体过程可能有一点细节

1.记录区间差分加的过程，要记录等差数列首项和公差，两个等差数列相加直接首项和公差都相加即可

2.区间赋值的优先级要高于加法，即打上赋值标记就要清空加法标记，标记下传时注意先下传赋值标记

然后具体问题落到如何实现插入元素这个操作上

块状链表

对于静态的数组，可以直接静态分块来做

而要动态插入时，找到对应块，插入即可，但是涉及到编号问题

所以需要每个块维护一个$Size$，块内每个元素维护一个标号$id_i$

同时需要对于块的$Size$累前缀和$SumSize$，则块$i$内编号为$j$的元素在数组中的实际编号为$SumSize_{i-1}+j$

插入时把整个块内的元素取出重新标号即可

但是这样插入后，一个块的$Size$会变大，再实现分块的操作时复杂度没有保证

因此需要加入一个操作:当$Size_i>2\sqrt n$时,$O(n)$重构整个序列，这样每$\sqrt n$次插入操作会导致一次重构，复杂度为均摊的$O(n\sqrt n)$

然后可以用类似分块的方法来直接维护

线段树

静态的操作线段树可以直接维护

在线段树上额外维护一个01，表示这个元素是否出现

将插入操作转化为在让对应位置的0变为1，但是由于不知道插入后的位置，所以不能直接操作

于是有两种解决办法

暴力值域

静态情况下我们对于$[1,n]$建树，但是动态可以对于$[1,n\cdot q]$建函数式线段树

离线

离线维护，预处理出插入的位置

平衡树

下面是安利时间

来学Treap吧

它可以

1.查询k大

2.插入元素

3.区间修改

4.区间翻转

5.可持久化!!

6.吊打Splay

Treap 即树堆，意思是在满足二叉查找树的性质同时满足二叉堆的性质

给定每个节点一个额外的随机权值，让二叉查找树对于这个权值满足堆的性质即可

这样构造的二叉查找树，树高是$O(\log n)$的

带旋Treap

像普通二叉查找树一样每次插入节点到叶子位置后，可能不满足二叉堆的性质，因此需要不断向上zig/zag来调整满足

区间操作可以尝试像写线段树一样写

但是它不可持久化

非旋Treap

维护两个基础操作

1.平衡树合并，操作需要满足两棵树的大小顺序确定，返回新的根

2.平衡树分裂为$[1,d],[d+1,n]$的两部分，返回两棵树的根

1.合并操作$x,y$

按照节点的权值比较谁是平衡树的根，然后将根的左/右子树与另一棵树合并作为新的子树，递归实现

2.分裂$x,d$

维护$Size$判断是要分裂左子树还是右子树，将子树分裂得到的部分作为$x$新的子树，递归实现即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef pair <int,int> Pii;
#define mp make_pair
int Union(int x,int y) {
	if(!x || !y) return x|y;
	Down(x),Down(y);
	if(key[x]<key[y]) return rs[x]=Union(rs[x],y),Up(x),x;
	return ls[y]=Union(x,ls[y]),Up(y),y;
}

Pii Split(int x,int d){
	if(!x) return mp(x,x);
	if(sz[x]<=d) return mp(x,0);
	if(d==0) return mp(0,x);
	Down(x);
	if(sz[ls[x]]+1<=d) {
		Pii y=Split(rs[x],d-sz[ls[x]]-1);
		return rs[x]=y.first,Up(x),mp(x,y.second);
	} else {
		Pii y=Split(ls[x],d);
		return ls[x]=y.second,Up(x),mp(y.first,x);
	}
}

插入操作可以分裂前$k$个，将新节点和得到的两棵树按次合并

区间更新可以分裂两次，将对应区间的子树操作即可

Code

块状链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
 
 
char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}
 
const int N=2e5+10;
 
int n,m,cnt;
int head[N],nxt[N],sz[N];
struct Node{ int rk,id; } E[N];
ll s[N],st[N],t[N],d[N],a[N]; 
int ssz[N];
 
ll Get(ll l,ll r){ return (r-l+1)*(l+r)/2; }
void Down(int p) {
    s[p]=0;
    for(int i=head[p];i;i=nxt[i]) {
        if(~st[p]) a[E[i].id]=st[p];
        a[E[i].id]+=1ll*(E[i].rk-1)*d[p]+t[p];
        s[p]+=a[E[i].id];
    }
    st[p]=-1,t[p]=d[p]=0;
}
void Up(int p) {
    s[p]=0;
    for(int i=head[p];i;i=nxt[i]) s[p]+=a[E[i].id];
}
 
void Build() {
    sort(E+1,E+n+1,[&](Node x,Node y){ return x.rk<y.rk; });
    rep(i,0,cnt) sz[i]=head[i]=0,st[i]=-1;
    rep(i,1,n) {
        int p=i/cnt+1;
        nxt[i]=head[p],E[i].rk=++sz[p];
        head[p]=i;
    }
    rep(i,1,cnt) ssz[i]=ssz[i-1]+sz[i],Up(i);
}
 
void Break(){
    rep(i,1,cnt) {
        sz[i]+=sz[i-1],Down(i);
        for(int j=head[i];j;j=nxt[j]) E[j].rk+=sz[i-1];
    }
    Build();
}
 
int Get(int x){
    x--;
    int l=1;
    while(sz[l]<=x) x-=sz[l++];
    return l;
}
 
void Insert(int p,int x){
    int l=p<=n?Get(p):cnt;
    Down(l),p-=ssz[l-1];
    for(int i=head[l];i;i=nxt[i]) if(E[i].rk>=p) E[i].rk++;
    a[++n]=x,E[n]=(Node){p,n},nxt[n]=head[l],head[l]=n;
    sz[l]++,s[l]+=x;
    if(sz[l]>cnt*2.4) Break();
    rep(i,1,cnt) ssz[i]=ssz[i-1]+sz[i];
}
 
void Set(int l,int r,int x) {
    int p1=Get(l),p2=Get(r);
    if(p1==p2) {
        Down(p1);
        for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l && ssz[p1-1]+E[i].rk<=r) a[E[i].id]=x;
        Up(p1);
        return;
    }
    Down(p1),Down(p2);
    s[p1]=s[p2]=0;
    for(int i=head[p1];i;i=nxt[i]) {
        if(ssz[p1-1]+E[i].rk>=l) a[E[i].id]=x;
        s[p1]+=a[E[i].id];
    }
    for(int i=head[p2];i;i=nxt[i]) {
        if(ssz[p2-1]+E[i].rk<=r) a[E[i].id]=x;
        s[p2]+=a[E[i].id];
    }
    rep(i,p1+1,p2-1) st[i]=x,d[i]=t[i]=0,s[i]=1ll*x*sz[i];
}
 
void Add(int l,int r,int x) {
    int p1=Get(l),p2=Get(r);
    if(p1==p2) {
        Down(p1);
        for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l && ssz[p1-1]+E[i].rk<=r) a[E[i].id]+=1ll*(ssz[p1-1]+E[i].rk-l+1)*x;
        Up(p1);
        return;
    }
    Down(p1),Down(p2);
    s[p1]=s[p2]=0;
    for(int i=head[p1];i;i=nxt[i]) {
        if(ssz[p1-1]+E[i].rk>=l) a[E[i].id]+=1ll*(ssz[p1-1]+E[i].rk-l+1)*x;
        s[p1]+=a[E[i].id];
    }
    for(int i=head[p2];i;i=nxt[i]) {
        if(ssz[p2-1]+E[i].rk<=r) a[E[i].id]+=1ll*(ssz[p2-1]+E[i].rk-l+1)*x;
        s[p2]+=a[E[i].id];
    }
    rep(i,p1+1,p2-1) {
        t[i]+=1ll*(ssz[i-1]-l+2)*x,d[i]+=x;
        s[i]+=Get(ssz[i-1]-l+2,ssz[i]-l+1)*x;
    }
}
 
ll Que(int l,int r) {
    int p1=Get(l),p2=Get(r);
    ll ans=0;
    Down(p1),Down(p2);
    if(p1==p2) {
        Down(p1);
        for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l && ssz[p1-1]+E[i].rk<=r) ans+=a[E[i].id];
        return ans;
    }
    Down(p1),Down(p2);
    for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l) ans+=a[E[i].id];
    for(int i=head[p2];i;i=nxt[i]) if(ssz[p2-1]+E[i].rk<=r) ans+=a[E[i].id];
    rep(i,p1+1,p2-1) ans+=s[i];
    return ans;
}
 
int main(){
    n=rd(),m=rd();
    cnt=ceil(sqrt(n+m));
    rep(i,1,n) a[i]=rd(),E[i]=(Node){i,i};
    Build();
    rep(i,1,m) {
        int opt=rd();
        if(opt==1) {
            int l=rd(),r=rd(),x=rd();
            Set(l,r,x);
        } else if(opt==2) {
            int l=rd(),r=rd(),x=rd();
            Add(l,r,x);
        } else if(opt==3) {
            int p=rd(),x=rd();
            Insert(p,x);
        } else if(opt==4) {
            int l=rd(),r=rd();
            printf("%lld\n",Que(l,r));
        }
    }
}

旋Treap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }


char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10;

int n;
int rt,son[N][2],fa[N];
ll s[N],t[N],d[N],st[N],val[N];
ll sz[N],key[N];

void Up(int p) {
	s[p]=s[son[p][0]]+s[son[p][1]]+val[p];
	sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
void Set(int p,ll x){
	t[p]=d[p]=0,st[p]=val[p]=x,s[p]=sz[p]*x;
}
void Add(int p,ll x,ll d) {
	val[p]+=x+d*sz[son[p][0]];
	s[p]+=sz[p]*(sz[p]-1)/2*d+x*sz[p];
	t[p]+=x,::d[p]+=d;
}
void Down(int p) {
	if(~st[p]) Set(son[p][0],st[p]),Set(son[p][1],st[p]),st[p]=-1;
	if(t[p] || d[p]) Add(son[p][0],t[p],d[p]),Add(son[p][1],t[p]+(sz[son[p][0]]+1)*d[p],d[p]),t[p]=d[p]=0;
}

void rotate(int u) {
	int f=fa[u],ff=fa[f],d=son[f][1]==u;
	fa[u]=ff; if(ff) son[ff][son[ff][1]==f]=u;
	son[f][d]=son[u][!d]; if(son[u][!d]) fa[son[u][!d]]=f;
	son[u][!d]=f,fa[f]=u;
	Up(f),Up(u);
}

void Insert(int p,int x){
	int v=++n;
	val[v]=s[v]=x,sz[v]=1,st[v]=-1,key[v]=rand();
	if(!rt){ rt=v; return; }
	int u=rt;
	while(u) {
		Down(u);
		if(sz[son[u][0]]>=p) {
			if(!son[u][0]) { son[fa[v]=u][0]=v; break; }
			u=son[u][0]; 
		} else {
			p-=sz[son[u][0]]+1;
			if(!son[u][1]) { son[fa[v]=u][1]=v; break; }
			u=son[u][1];
		}
	}
	while(fa[v] && key[v]<key[fa[v]]) rotate(v);
	if(!fa[v]) rt=v;
	while(fa[v]) Up(v=fa[v]);
}

void Set(int p,int l,int r,int x) {
	if(!p || r<=0 || l>sz[p]) return;
	if(l<=1 && r>=sz[p]) return Set(p,x);
	int t=sz[son[p][0]]+1;
	Down(p),Set(son[p][0],l,r,x),Set(son[p][1],l-t,r-t,x);
	if(t>=l && t<=r) val[p]=x;
	Up(p);
}

void Add(int p,int l,int r,ll x,ll d) {
	if(!p || r<=0 || l>sz[p]) return;
	if(l<=1 && r>=sz[p]) return Add(p,x,d);
	int t=sz[son[p][0]]+1;
	Down(p),Add(son[p][0],l,r,x,d),Add(son[p][1],l-t,r-t,x+d*t,d);
	if(t>=l && t<=r) val[p]+=(t-1)*d+x;
	Up(p);
}

ll Que(int p,int l,int r) {
	if(!p || r<=0 || l>sz[p]) return 0;
	if(l<=1 && r>=sz[p]) return s[p];
	ll t=sz[son[p][0]]+1,res=0;
	Down(p),res+=Que(son[p][0],l,r),res+=Que(son[p][1],l-t,r-t);
	if(t>=l && t<=r) res+=val[p];
	return res;
}

int main(){
	int n=rd(),m=rd();
	rep(i,0,n-1) Insert(i,rd());
	while(m--) {
		int opt=rd();
		if(opt==1) {
			int l=rd(),r=rd();
			Set(rt,l,r,rd());
		} else if(opt==2) {
			int l=rd(),r=rd(),x=rd();
			Add(rt,l,r,x-1ll*(l-1)*x,x);
		} else if(opt==3) {
			int x=rd(),y=rd();
			Insert(x-1,y);
		} else {
			int l=rd(),r=rd();
			printf("%lld\n",Que(rt,l,r));
		}
	}
}



非旋Treap:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define mp make_pair
int rd(){
    char c;int s=0;
    while((c=getchar())<48);
    do s=s*10+c-48;
    while((c=getchar())>47);
    return s;
}
enum{N=200010};
int n,m,rt,ls[N],rs[N],key[N];
ll s[N],t[N],d[N],st[N],val[N],sz[N];
 
inline void Up(int p) {
    s[p]=s[ls[p]]+s[rs[p]]+val[p];
    sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
inline void Set(int p,ll x){ t[p]=d[p]=0,st[p]=val[p]=x,s[p]=sz[p]*x; }
inline void Add(int p,ll x,ll d) {
    val[p]+=x+d*sz[ls[p]];
    s[p]+=sz[p]*(sz[p]-1)/2*d+x*sz[p];
    t[p]+=x,::d[p]+=d;
}
inline void Down(int p) {
    ~st[p] && (Set(ls[p],st[p]),Set(rs[p],st[p]),st[p]=-1);
    (t[p] || d[p]) && (Add(ls[p],t[p],d[p]),Add(rs[p],t[p]+(sz[ls[p]]+1)*d[p],d[p]),t[p]=d[p]=0);
}
int Union(int x,int y) {
    if(!x || !y) return x|y;
    return key[x]<key[y]?(Down(x),rs[x]=Union(rs[x],y),Up(x),x):(Down(y),ls[y]=Union(x,ls[y]),Up(y),y);
}
Pii Split(int x,int d){
    if(sz[x]<=d) return mp(x,0);
    if(d==0) return mp(0,x);
    Down(x);
    if(sz[ls[x]]+1<=d) {
        Pii y=Split(rs[x],d-sz[ls[x]]-1);
        return rs[x]=y.first,Up(x),mp(x,y.second);
    } else {
        Pii y=Split(ls[x],d);
        return ls[x]=y.second,Up(x),mp(y.first,x);
    }
}
 
int main(){
    n=rd(),m=rd();
    for(int i=1;i<=n+m;++i) key[i]=rand(),st[i]=-1,sz[i]=1;
    for(int i=1;i<=n;++i) val[i]=s[i]=rd(),rt=Union(rt,i);
    while(m--){
        int opt=rd();
        if(opt==3) {
            Pii t=Split(rt,rd()-1); ++n,val[n]=s[n]=rd();
            rt=Union(Union(t.first,n),t.second);
        } else {
            int l=rd(),r=rd();
            Pii a=Split(rt,l-1),b=Split(a.second,r-l+1);
            if(opt==1) Set(b.first,rd());
            else if(opt==2) {int x=rd(); Add(b.first,x,x); }
            else if(opt==4) printf("%lld\n",s[b.first]);
            rt=Union(Union(a.first,b.first),b.second);
        }
    }
}