```cpp
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
const ll inf=0x7ffffffffffff;
const ll mod=1e9+7;
#define N 500050
queue<int> trash;
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
return x*f;
}
ll n,m,root,cnt=0;
struct node{
ll ch[2],siz,to,val,key,sum,add,cov,use;
bool rev,isu;
void Reverse(){
rev^=1;
//swap(ch[0],ch[1]);
}
void Add(ll c){
add=(add+c)%mod;
val=(val+c)%mod;
sum=(sum+siz*c)%mod;
}
void Cover(ll c){
val=cov=c;
add=0;
sum=siz*c%mod;
}
}t[N*30];//N+N*log2(N)
void pushdown(ll);
void Del(int k){
trash.push(k);
if(t[k].to!=inf)t[t[k].to].use--;
if(t[k].ch[0])Del(t[k].ch[0]);
if(t[k].ch[1])Del(t[k].ch[1]);
}
ll NewNode(ll data,ll to){
ll k;
if(!trash.empty()){
k=trash.front(),trash.pop();
if(t[k].to){
t[t[k].to].use--;
if(t[t[k].to].use==0){
trash.push(t[k].to);
}
}
//pushdown(k);
//if(t[k].ch[0]&&!t[t[k].ch[0]].isu)trash.push(t[k].ch[0]);
//if(t[k].ch[1]&&!t[t[k].ch[1]].isu)trash.push(t[k].ch[1]);
}
else k=++cnt;
t[k].key=rand();
t[k].siz=1;
t[k].to=to;
t[k].cov=inf;
t[k].ch[1]=t[k].ch[0]=t[k].add=0;
t[k].val=t[k].sum=data%mod;
t[k].rev=t[k].isu=false;
t[k].use=inf;
return k;
}
void inher(ll p,ll q){
t[p].key=t[q].key;
t[p].siz=t[q].siz;
t[p].sum=t[q].sum%mod;
t[p].cov=t[q].cov;
t[p].add=t[q].add;
t[p].val=t[q].val;
t[p].rev=t[q].rev;
}
void update(ll k){
if(!k)return;
if(t[k].to==inf){
t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+1;
t[k].sum=(t[t[k].ch[0]].sum+t[t[k].ch[1]].sum+t[k].val)%mod;
}
else{
t[k].siz=t[t[k].to].siz;
t[k].sum=t[t[k].to].sum%mod;
}
}
void pushdown(ll k){
if(!k)return;
//cout<<k<<endl;
if(t[k].isu){
if(t[k].ch[0]&&!t[t[k].ch[0]].isu)t[t[k].ch[0]].isu=true,t[t[k].ch[0]].use=2;
if(t[k].ch[1]&&!t[t[k].ch[1]].isu)t[t[k].ch[1]].isu=true,t[t[k].ch[1]].use=2;
}
if(t[k].to!=inf){
pushdown(t[t[k].to].ch[0]),pushdown(t[t[k].to].ch[1]);
//pushdown(t[k].to);
if(t[t[k].to].ch[0])t[k].ch[0]=NewNode(inf,t[t[k].to].ch[0]),inher(t[k].ch[0],t[t[k].to].ch[0]);
if(t[t[k].to].ch[1])t[k].ch[1]=NewNode(inf,t[t[k].to].ch[1]),inher(t[k].ch[1],t[t[k].to].ch[1]);
//t[t[k].to].use--;
//if(t[t[k].to].use==0){
// trash.push(t[k].to);
//}
t[k].to=inf;
}
if(t[k].rev){
swap(t[k].ch[0],t[k].ch[1]);
if(t[k].ch[0])/*pushdown(t[k].ch[0]),*/t[t[k].ch[0]].Reverse();
if(t[k].ch[1])/*pushdown(t[k].ch[1]),*/t[t[k].ch[1]].Reverse();
t[k].rev^=1;
}
if(t[k].cov!=inf){
if(t[k].ch[0])t[t[k].ch[0]].Cover(t[k].cov);
if(t[k].ch[1])t[t[k].ch[1]].Cover(t[k].cov);
t[k].cov=inf;
}
if(t[k].add){
if(t[k].ch[0])t[t[k].ch[0]].Add(t[k].add);
if(t[k].ch[1])t[t[k].ch[1]].Add(t[k].add);
t[k].add=0;
}
}
ll Merge(ll l,ll r){
if(!l||!r)return l+r;
pushdown(l),pushdown(r);
if(t[l].key<t[r].key){
t[l].ch[1]=Merge(t[l].ch[1],r);
update(l);
return l;
}
else{
t[r].ch[0]=Merge(l,t[r].ch[0]);
update(r);
return r;
}
}
void Split(ll k,ll data,ll &l,ll &r){
if(!k){
l=r=0;
return ;
}
pushdown(k);
if(t[t[k].ch[0]].siz+1<=data){
l=k;
Split(t[k].ch[1],data-t[t[k].ch[0]].siz-1,t[k].ch[1],r);
}
else{
r=k;
Split(t[k].ch[0],data,l,t[k].ch[0]);
}
update(k);
}
ll get_sum(ll x,ll y){
ll l=0,p=0,r=0;
Split(root,y,l,r);
Split(l,x-1,l,p);
ll ans=t[p].sum%mod;
root=Merge(Merge(l,p),r);
return ans;
}
void Reverse(ll x,ll y){
ll l=0,p=0,r=0;
Split(root,y,l,r);
Split(l,x-1,l,p);
t[p].Reverse();
root=Merge(Merge(l,p),r);
}
void Add(ll x,ll y,ll c){
ll l=0,p=0,r=0;
Split(root,y,l,r);
Split(l,x-1,l,p);
t[p].Add(c);
root=Merge(Merge(l,p),r);
}
void Cover(ll x,ll y,ll c){
ll l=0,p=0,r=0;
Split(root,y,l,r);
Split(l,x-1,l,p);
t[p].Cover(c);
root=Merge(Merge(l,p),r);
}
void Copy(ll l1,ll r1,ll l2,ll r2){
//l p mid q r p->q
ll l=0,p=0,mid=0,q=0,r=0;
if(l1>l2){
Split(root,r1,l,r);
Split(l,l1-1,l,q);
Split(l,r2,l,mid);
Split(l,l2-1,l,p);
swap(p,q);
}
else{
Split(root,r2,l,r);
Split(l,l2-1,l,q);
Split(l,r1,l,mid);
Split(l,l1-1,l,p);
}
//trash.push(q);
//pushdown(p);
//Del(q);
ll n1=NewNode(inf,p),n2=NewNode(inf,p);
inher(n1,p),inher(n2,p);
t[p].isu=true,t[p].use=2;
//dfs(p,q);
root=Merge(Merge(l,n1),Merge(mid,Merge(n2,r)));
}
void Swap(ll l1,ll r1,ll l2,ll r2){
ll l=0,r=0,p=0,mid=0,q=0;
if(l1>l2){
swap(l1,l2),swap(r1,r2);
}
Split(root,r2,l,r);
Split(l,l2-1,l,q);
Split(l,r1,l,mid);
Split(l,l1-1,l,p);
root=Merge(Merge(l,q),Merge(mid,Merge(p,r)));
}
void Output(ll k){
pushdown(k);
if(t[k].ch[0])Output(t[k].ch[0]);
cout<<t[k].val%mod<<" ";
if(t[k].ch[1])Output(t[k].ch[1]);
}
int main(){
freopen("fuck.in","r",stdin);//请理解我的感受QWQ
//freopen("f1.out","w",stdout);
n=read(),m=read();
for(ll i=1;i<=n;i++){
root=Merge(root,NewNode(read(),inf));
}
for(ll i=1;i<=m;i++){
ll opt=read();
if(opt==1){
ll l=read(),r=read();
cout<<get_sum(l,r)<<endl;
}
else if(opt==2){
ll l=read(),r=read(),c=read();
Cover(l,r,c);
}
else if(opt==3){
ll l=read(),r=read(),c=read();
Add(l,r,c);
}
else if(opt==4){
ll l1=read(),r1=read(),l2=read(),r2=read();
Copy(l1,r1,l2,r2);
}
else if(opt==5){
ll l1=read(),r1=read(),l2=read(),r2=read();
Swap(l1,r1,l2,r2);
}
else if(opt==6){
ll l=read(),r=read();
Reverse(l,r);
}
//cout<<" "<<cnt<<endl;
}
Output(root);
cout<<endl<<cnt<<endl;
return 0;
}
```
by Froggy @ 2019-06-16 16:46:47
你已经是个优秀的程序员了,你要学会自己DeBug了
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
#define MAXN 1000000
int n, opt, a, cnt, root, x, y, z;
struct node {
int l, r, val, key, size;
} t[MAXN];
inline int read() {
int s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
return s * w;
}
inline int New(int val) {
t[++cnt].val = val, t[cnt].key = rand() * rand(), t[cnt].size = 1;
return cnt;
}
inline void update(int now) {
t[now].size = t[t[now].l].size + t[t[now].r].size + 1;
}
inline void Split(int now, int w, int &u, int &v) {
if (!now) u = v = 0;
else {
if (t[now].val <= w) u = now, Split(t[now].r, w, t[u].r, v);
else v = now, Split(t[now].l, w, u, t[v].l);
update(now);
}
}
inline int Merge(int u, int v) {
if (!u || !v) return u + v;
if (t[u].key < t[v].key) {
t[u].r = Merge(t[u].r, v);
update(u);
return u;
}
else {
t[v].l = Merge(u, t[v].l);
update(v);
return v;
}
}
inline void Insert(int val) {
int x, y;
Split(root, val, x, y);
root = Merge(Merge(x, New(val)), y);
}
inline int Kth(int now, int sum) {
while (1) {
if (sum <= t[t[now].l].size) now = t[now].l;
else if (sum == t[t[now].l].size + 1) return now;
else sum -= t[t[now].l].size + 1 , now = t[now].r;
}
}
int main() {
srand(time(0));
n = read();
while (n--) {
opt = read(), a = read();
switch (opt) {
case 1 : {
Insert(a);
break;
}
case 2 : {
Split(root, a, x, z);
Split(x, a - 1, x, y);
y = Merge(t[y].l, t[y].r);
root = Merge(Merge(x, y), z);
break;
}
case 3 : {
Split(root, a - 1, x, y);
printf("%d\n", t[x].size + 1);
root = Merge(x, y);
break;
}
case 4 : {
printf("%d\n", t[Kth(root, a)].val);
break;
}
case 5 : {
Split(root, a - 1, x, y);
printf("%d\n", t[Kth(x, t[x].size)].val);
root = Merge(x, y);
break;
}
case 6 : {
Split(root, a, x, y);
printf("%d\n", t[Kth(y, 1)].val);
root = Merge(x, y);
break;
}
}
}
return 0;
}
```
by Agakiss @ 2019-06-16 16:56:36
@[Code_Note](/space/show?uid=31069)
# 你发的代码是什么鬼鬼????
by Froggy @ 2019-06-16 17:00:23
4操作咋保证的复杂度呀...
by x_angelkawaii_x @ 2019-06-16 17:14:24
@[沉迷学习的YSJ](/space/show?uid=93483)
把l1~l2拆出来,分别在两个地方动态开点,记录l1~l2的根
by Froggy @ 2019-06-16 17:23:23
@[Froggy](/space/show?uid=100285)
你动态开什么点.
by x_angelkawaii_x @ 2019-06-16 17:56:43
@[Froggy](/space/show?uid=100285) 你这样会导致出现key相同的点,这种情况复杂度会有问题,这题要写treap的话要随机合并
by 142857cs @ 2019-06-16 17:57:34
@[142857cs](/space/show?uid=35760) 怎么随机合并
by Froggy @ 2019-06-16 18:06:30
```cpp
if(rand%(t[l].size+t[r].size)<t[l].size){
t[l].ch[1]=Merge(t[l].ch[1],r);
update(l);
return l;
}
else{
t[r].ch[0]=Merge(l,t[r].ch[0]);
update(r);
return r;
}
```
@[Froggy](/space/show?uid=100285)
by 142857cs @ 2019-06-16 18:17:34
@[142857cs](/space/show?uid=35760) 谢谢,但还是步星QWQ
by Froggy @ 2019-06-16 18:27:40