ODT 珂朵莉树
如果你不会，你可以看看：ODT 珂朵莉树。
数据随机，且有区间赋值，因此考虑 ODT。
操作 $1\sim3$ 是简单的，考虑操作 $4\sim6$。
操作 $4$：区间复制
区间不交，分别 split 操作后，暴力记录 $[l_1,r_1]$ 的信息，删除 $[l_2,r_2]$ 的信息再插入记录信息即可。
同时注意区间端点需要偏移，偏移量为 $l_2-l_1=r_2-r_1$。
操作 $5$：区间交换
区间交换，可以分别记录两个区间的信息，删除原信息后插入即可。
同时注意端点需要偏移，偏移量为 $\pm(l_2-l_1)=\pm(r_2-r_1)$。
操作 $6$：区间翻转
在区间 $[l,r]$ 内有多个区间 $[l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]$，需要翻转。
发现翻转得到的 $[l_i’,r_i’]$ 相对于原区间 $[l_i,r_i]$，有：
\(\begin{aligned} l_i'&=l+r-r_i\\ r_i'&=l+r-l_i \end{aligned}\) 因此可以记录信息，删除后插入。
AC 代码
注意迭代器失效问题。
放一组数据供调试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
20 20
304918551 41464763 626731291 93384272 932133547 58912715 131988999 702069776 263423490 347646978 59122396 563111221 416760930 459270045 184611400 242744859 821538911 367584997 718440022 971034462
4 11 13 5 7
6 5 10
2 14 20 185648890
2 8 13 39249510
1 2 15
1 3 5
5 10 11 15 16
4 5 7 17 19
6 5 15
3 9 19 742600878
6 4 4
3 1 17 13105838
5 3 5 13 15
3 3 9 720875841
3 7 11 551893354
1 10 20
5 1 6 8 13
5 4 8 11 15
6 4 17
2 2 13 341469949
1
2
3
4
681515396
67762534
968391129
325124536 341469949 341469949 341469949 341469949 341469949 341469949 341469949 341469949 341469949 341469949 341469949 341469949 106490110 919630569 824229528 740006040 6024361 444670647 185648890
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
176
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<set>
using namespace std;
typedef long long ll;
constexpr const int N=1e5,P=1e9+7;
int n;
struct ODT{
struct node{
int l,r;
mutable int value;
};
friend bool operator <(node a,node b){
return a.l<b.l;
}
set<node>t;
void build(int l,int r){
t.clear();
t.insert({l,r+1});
}
auto split(int x){
auto p=t.lower_bound({x});
if(p!=t.end()&&p->l==x){
return p;
}
p=prev(p);
int l=p->l,r=p->r,value=p->value;
t.erase(p);
t.insert({l,x-1,value});
return t.insert({x,r,value}).first;
}
void assign(int l,int r,int value){
auto pr=split(r+1);
auto pl=split(l);
t.erase(pl,pr);
t.insert({l,r,value});
}
void add(int l,int r,int x){
auto pr=split(r+1);
auto pl=split(l);
for(auto i=pl;i!=pr;i=next(i)){
i->value=(i->value + x)%P;
}
}
int sum(int l,int r){
auto pr=split(r+1);
auto pl=split(l);
int ans=0;
for(auto i=pl;i!=pr;i=next(i)){
ans=(ans + i->value * (i->r - i->l + 1ll) )%P;
}
return ans;
}
void copy(int l1,int r1,int l2,int r2){
auto pr1=split(r1+1);
auto pl1=split(l1);
vector<node>s;
for(auto i=pl1;i!=pr1;i=next(i)){
s.push_back(*i);
}
auto pr2=split(r2+1);
auto pl2=split(l2);
t.erase(pl2,pr2);
for(auto i:s){
t.insert({i.l+l2-l1,i.r+r2-r1,i.value});
}
}
void swap(int l1,int r1,int l2,int r2){
if(l1>l2){
std::swap(l1,l2);
std::swap(r1,r2);
}
auto pr2=split(r2+1);
auto pl2=split(l2);
auto pr1=split(r1+1);
auto pl1=split(l1);
vector<node>s1,s2;
for(auto i=pl1;i!=pr1;i=next(i)){
s1.push_back(*i);
}
for(auto i=pl2;i!=pr2;i=next(i)){
s2.push_back(*i);
}
t.erase(pl1,pr1);
pr2=split(r2+1);
pl2=split(l2);
t.erase(pl2,pr2);
for(auto i:s1){
t.insert({i.l+l2-l1,i.r+r2-r1,i.value});
}
for(auto i:s2){
t.insert({i.l+l1-l2,i.r+r1-r2,i.value});
}
}
void reverse(int l,int r){
if(l>r){
std::swap(l,r);
}
auto pr=split(r+1);
auto pl=split(l);
vector<node>s;
for(auto i=pl;i!=pr;i=next(i)){
s.push_back(*i);
}
t.erase(pl,pr);
for(auto i:s){
t.insert({l+r-i.r,l+r-i.l,i.value});
}
}
}t;
main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int m;
cin>>n>>m;
t.build(1,n);
for(int i=1;i<=n;i++){
int a;
cin>>a;
t.assign(i,i,a);
}
while(m--){
int op,l1,r1,l2,r2,x;
cin>>op>>l1>>r1;
switch(op){
case 1:
cout<<t.sum(l1,r1)<<'\n';
break;
case 2:
cin>>x;
t.assign(l1,r1,x);
break;
case 3:
cin>>x;
t.add(l1,r1,x);
break;
case 4:
cin>>l2>>r2;
t.copy(l1,r1,l2,r2);
break;
case 5:
cin>>l2>>r2;
t.swap(l1,r1,l2,r2);
break;
case 6:
t.reverse(l1,r1);
break;
}
}
for(int i=1;i<=n;i++){
cout<<t.sum(i,i)<<' ';
}
cout<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
