区间赋值？数据随机？
——珂朵莉树！
不愧是 STL，不吸氧 TLE 70pts，吸氧轻松跑进一秒半。
（小声 BB：洛谷提交时「使用 O2 优化」的选项比手动 pragma 要快很多。）
前三个操作都很套路，注意取模。
重点讨论后三个。（其实也不难啊）
复制操作，显然对于 \(i \in [l_1,r_1]\)，其在 \([l_2,r_2]\) 中对应的位置是 \(i - l_1 + l_2\)。
所以可以先把 \([l_1,r_1]\) 里的东西提出来，再删掉 \([l_2,r_2]\) 里的东西，然后插入。
交换操作，类似地先把两个区间的东西提出来放到 vector 里，然后删除两个区间原来有的再把新的插回去。
翻转操作，对于 \(i \in [l,r]\)，其反转后所在的位置是 \(l + r - i\)，于是类比之前的操作提出来删掉再放回去即可。
代码： 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
using namespace std;
const int N = 3e5;
const int mod = 1e9 + 7;
int n,m;
struct node
{
int l,r;
mutable int v;
inline bool operator<(const node &o) const
{
return l < o.l;
}
};
typedef set<node>::iterator IT;
set<node> d;
vector<node> vec;
IT split(int x)
{
if(x > n)
return d.end();
IT it = --d.upper_bound((node){x,0,0});
if(it->l == x)
return it;
int l = it->l,r = it->r,v = it->v;
d.erase(it);
d.insert((node){l,x - 1,v});
return d.insert((node){x,r,v}).first;
}
int query(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
int ret = 0;
for(register IT it = itl;it != itr;++it)
ret = (ret + (long long)it->v * (it->r - it->l + 1) % mod) % mod;
return ret;
}
void assign(int l,int r,int v)
{
IT itr = split(r + 1),itl = split(l);
d.erase(itl,itr);
d.insert((node){l,r,v});
}
void update(int l,int r,int v)
{
IT itr = split(r + 1),itl = split(l);
for(register IT it = itl;it != itr;++it)
it->v = (it->v + v) % mod;
}
void copy(int l1,int r1,int l2,int r2)
{
IT itr = split(r1 + 1),itl = split(l1);
vec.clear();
for(register IT it = itl;it != itr;++it)
vec.push_back((node){it->l - l1 + l2,it->r - l1 + l2,it->v});
itr = split(r2 + 1),itl = split(l2);
d.erase(itl,itr);
for(register int i = 0;i < vec.size();++i)
d.insert(vec[i]);
}
void swap(int l1,int r1,int l2,int r2)
{
if(l1 > l2)
swap(l1,l2),swap(r1,r2);
IT itr = split(r1 + 1),itl = split(l1);
vec.clear();
for(register IT it = itl;it != itr;++it)
vec.push_back((node){it->l - l1 + l2,it->r - l1 + l2,it->v});
d.erase(itl,itr);
itr = split(r2 + 1),itl = split(l2);
for(register IT it = itl;it != itr;++it)
vec.push_back((node){it->l - l2 + l1,it->r - l2 + l1,it->v});
d.erase(itl,itr);
for(register int i = 0;i < vec.size();++i)
d.insert(vec[i]);
}
void reverse(int l,int r)
{
IT itr = split(r + 1),itl = split(l);
vec.clear();
for(register IT it = itl;it != itr;++it)
vec.push_back((node){l + r - it->r,l + r - it->l,it->v});
d.erase(itl,itr);
for(register int i = 0;i < vec.size();++i)
d.insert(vec[i]);
}
int main()
{
scanf("%d%d",&n,&m);
int x;
for(register int i = 1;i <= n;++i)
scanf("%d",&x),d.insert((node){i,i,x});
int op,l1,r1,l2,r2,v;
while(m--)
{
scanf("%d%d%d",&op,&l1,&r1);
if(op == 1)
printf("%d\n",query(l1,r1));
else if(op == 2)
scanf("%d",&v),assign(l1,r1,v);
else if(op == 3)
scanf("%d",&v),update(l1,r1,v);
else if(op == 4)
scanf("%d%d",&l2,&r2),copy(l1,r1,l2,r2);
else if(op == 5)
scanf("%d%d",&l2,&r2),swap(l1,r1,l2,r2);
else
reverse(l1,r1);
}
for(register IT it = d.begin();it != d.end();++it)
for(register int i = it->l;i <= it->r;++i)
printf("%d ",it->v);
}