ODT
这道题目太毒瘤啦，经过了无数遍的TLE、WA，和RE(TAT)，我终于了解了珂朵莉树的强（R）大（E）,我会详细的介绍关于TLE，WA和RE的原因。
首先我们看到区间赋值操作和保证数据随机，我们的第一直觉肯定是珂朵莉树啦，虽然在刻意构造的数据下她的时间复杂度是错误的，但是在随机数据下她的表现十分优秀，甚至可以碾压其他数据结构。
1.首先是split操作，这是ODT的基本操作，可以将完整的区间拆分开来。但应注意的是，
if(it!=s.end()&&it->l==pos)return it;
所以我们需要在n的后面加上一个数防止出锅，
s.insert((node){n+1,n+1,(LL)0});
2.区间加、求和、推平，这些都是ODT模板上的操作，注意一下及时取模就珂以了。
3.让我们来看看新的操作：区间复制：根据zh_dou大佬的讲解，我们知道过期的迭代器是不能使用的，否则直接原地起飞。所以我们的做法就是将我们需要复制的区间先存起来，然后再删除了对应的区间后再将区间复制过去。
void fuzhi(int l1,int r1,int l2,int r2)
{
IT it1r=split(r1+1),it1l=split(l1);
int len=0;
for(IT it=it1l;it!=it1r;++it)
{
a[++len].l=it->l;
a[len].r=it->r;
a[len].val=it->val;
}
IT it2r=split(r2+1),it2l=split(l2);
s.erase(it2l,it2r);
for(int i=1;i<=len;++i)
{
s.insert(node(a[i].l - l1 + l2,a[i].r - l1 + l2,a[i].val));
}
}
4.新操作：区间翻转：还是根据迭代器的一套理论，我们应该先存起来在进行操作：
void fanzhuan(int l,int r)
{
if(l>r)swap(l,r);
IT it2=split(r+1),it1=split(l);
int len=0;
for(IT it=it1;it!=it2;++it)
{
a[++len].l=it->l;
a[len].r=it->r;
a[len].val=it->val;
}
s.erase(it1,it2);
for(int i=1;i<=len;++i)
{
s.insert(node(r-a[i].r+l, r-a[i].l+l, a[i].val));
}
}
5.毒瘤交换操作：这可能是最毒瘤的一种操作了，RE到我直接自闭。我们可以想像一下我们交换两个数的情景，就会发现这也同样适用于区间的交换，为了 好调bug 简洁明了，我用了两个数组来完成：
void my_swap(int l1,int r1,int l2,int r2)
{
if(l1>l2){swap(l1,l2);swap(r1,r2);}
int len1=0,len2=0;
IT it1r=split(r1+1),it1l=split(l1);
for(IT it=it1l;it!=it1r;++it)
{
a[++len1].l=it->l;
a[len1].r=it->r;
a[len1].val=it->val;
}
IT it2r=split(r2+1),it2l=split(l2);
for(IT it=it2l;it!=it2r;++it)
{
b[++len2].l=it->l;
b[len2].r=it->r;
b[len2].val=it->val;
}
it1r=split(r1+1),it1l=split(l1);
s.erase(it1l,it1r);
it2r=split(r2+1),it2l=split(l2);
s.erase(it2l,it2r);
for(int i=1;i<=len2;++i)s.insert(node(b[i].l - l2 + l1,b[i].r - l2 + l1,b[i].val));
for(int i=1;i<=len1;++i)s.insert(node(a[i].l - l1 + l2,a[i].r - l1 + l2,a[i].val));
}
然后每个数都要输出的话只用遍历一遍set就珂以啦~（当然你也珂以用来中间调试用）。
void pr()
{
for(IT it=s.begin();it!=s.end()&&it->r<=n;++it)
{
for(int i=it->l;i<=it->r;++i)printf("%lld ",it->val);
}
}
最后说几点需要注意的事情
1.过期的迭代器千万不要使用，否则自己怎么RE的都不知道，具体的操作就应该是在每次使用迭代器前就应该split一下，防止出锅。
2.遍历的时候最好再开一个迭代器千万不要这样写：
s.erase(it1,it2);
for(;it1!=it2;++it1)
{
s.insert(node(XXX,XXX,XXX));
}
不要问我为什么我知道(TAT).
3.要开long long，并且还需要及时取模。
4.函数传参不要传错。
5.最好在n+1的位置上加上一个数(珂以是0、233或者666，随你的心意啦)。
6.需要开O2，否则就死掉了QAQ
最后献上我的完整代码
#include<iostream>
#include<cstdio>
#include<set>
#define LL long long
#define IT set<node>::iterator
using namespace std;
int n,q,opt,l1,r1,l2,r2,l,r;
LL val,x;
const int mod=1e9+7,N=500010;
inline int read()
{
register int x=0,y=1;register char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')y=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*y;
}
struct node
{
int l,r;
mutable long long val;
node(int L=0,int R=-1,int V=0):l(L),r(R),val(V){}
friend bool operator <(const node &a,const node &b){return a.l<b.l;}
// int len(){return r-l+1;}
};
node a[N],b[N];
set<node>s;
IT split(int pos)
{
IT it=s.lower_bound(node(pos));
if(it!=s.end()&&it->l==pos)return it;
it--;
int ll=it->l,lr=it->r;
LL lv=it->val;
s.erase(it);
s.insert(node(ll,pos-1,lv));
return s.insert(node(pos,lr,lv)).first;
}
LL ask(int l,int r)
{
IT it2=split(r+1),it1=split(l);
LL ans=0;
for(IT it=it1;it!=it2;++it)
(ans+=(LL)(it->r - it->l + 1)*it->val)%=mod;
return ans;
}
void add(int l,int r,LL val)
{
IT it2=split(r+1),it1=split(l);
for(IT it=it1;it!=it2;++it)(it->val+=val)%=mod;
}
void tuiping(int l,int r,LL val)
{
IT it2=split(r+1),it1=split(l);
s.erase(it1,it2);
s.insert(node(l,r,val));
}
void fuzhi(int l1,int r1,int l2,int r2)
{
IT it1r=split(r1+1),it1l=split(l1);
int len=0;
for(IT it=it1l;it!=it1r;++it)
{
a[++len].l=it->l;
a[len].r=it->r;
a[len].val=it->val;
}
IT it2r=split(r2+1),it2l=split(l2);
s.erase(it2l,it2r);
for(int i=1;i<=len;++i)
{
s.insert(node(a[i].l - l1 + l2,a[i].r - l1 + l2,a[i].val));
}
}
void pr()
{
for(IT it=s.begin();it!=s.end()&&it->r<=n;++it)
{
for(int i=it->l;i<=it->r;++i)printf("%lld ",it->val);
}
}
void my_swap(int l1,int r1,int l2,int r2)
{
if(l1>l2){swap(l1,l2);swap(r1,r2);}
int len1=0,len2=0;
IT it1r=split(r1+1),it1l=split(l1);
for(IT it=it1l;it!=it1r;++it)
{
a[++len1].l=it->l;
a[len1].r=it->r;
a[len1].val=it->val;
}
IT it2r=split(r2+1),it2l=split(l2);
for(IT it=it2l;it!=it2r;++it)
{
b[++len2].l=it->l;
b[len2].r=it->r;
b[len2].val=it->val;
}
it1r=split(r1+1),it1l=split(l1);
s.erase(it1l,it1r);
it2r=split(r2+1),it2l=split(l2);
s.erase(it2l,it2r);
for(int i=1;i<=len2;++i)s.insert(node(b[i].l - l2 + l1,b[i].r - l2 + l1,b[i].val));
for(int i=1;i<=len1;++i)s.insert(node(a[i].l - l1 + l2,a[i].r - l1 + l2,a[i].val));
}
void fanzhuan(int l,int r)
{
if(l>r)swap(l,r);
IT it2=split(r+1),it1=split(l);
int len=0;
for(IT it=it1;it!=it2;++it)
{
a[++len].l=it->l;
a[len].r=it->r;
a[len].val=it->val;
}
s.erase(it1,it2);
for(int i=1;i<=len;++i)
{
s.insert(node(r-a[i].r+l, r-a[i].l+l, a[i].val));
}
}
int main()
{
n=read(),q=read();
for(int i=1;i<=n;++i)
{
scanf("%lld",&x);
s.insert(node(i,i,x));
}
s.insert((node){n+1,n+1,(LL)0});
while(q--)
{
opt=read();
if(opt==1)
{
l=read();r=read();
printf("%lld\n",ask(l,r));
}
if(opt==2)
{
l=read();r=read();scanf("%lld",&val);
tuiping(l,r,val);
}
if(opt==3)
{
l=read();r=read();scanf("%lld",&val);
add(l,r,val);
}
if(opt==4)
{
l1=read();r1=read();l2=read();r2=read();
fuzhi(l1,r1,l2,r2);
}
if(opt==5)
{
l1=read();r1=read();l2=read();r2=read();
my_swap(l1,r1,l2,r2);
}
if(opt==6)
{
l=read();r=read();
fanzhuan(l,r);
}
}
pr();
return 0;
}
京公网安备 11010502036488号