- 从头到尾看了好几遍,没有 UB 啊....../kk
- 难道此题像许多题一样 凉心地卡掉了珂朵莉树......
珂怜的珂朵莉
- 开 O2 前
- 开 O2 后
- 代码在这里:
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<set>
#include<vector>
#define LL long long
const LL p=1000000007;
using namespace std;
struct Node{
LL l,r;
mutable LL val;
Node(LL L,LL R,LL V):l(L),r(R),val(V){}
Node(LL L):l(L){}
bool operator<(const Node &o)const{
return l<o.l;
}
};
set<Node>s;
LL n,m;
#define Sit set<Node>::iterator
Sit split(LL pos){
Sit it=s.lower_bound(Node(pos));
if(it!=s.end()&&it->l==pos){
return it;
}
it--;
LL L=it->l,R=it->r,V=it->val;
s.erase(it);
s.insert(Node(L,pos-1,V));
return s.insert(Node(pos,R,V)).first;
}
inline void assign(LL l,LL r,LL k){
k%=p;
Sit itr=split(r+1),itl=split(l);
s.erase(itl,itr);
s.insert(Node(l,r,k));
}
inline void add(LL l,LL r,LL k){
Sit itr=split(r+1),itl=split(l);
for(Sit it=itl;it!=itr;it++){
it->val+=k;
it->val%=p;
}
}
inline LL query(LL l,LL r){
LL ans=0;
Sit itr=split(r+1),itl=split(l);
for(Sit it=itl;it!=itr;it++){
ans+=(it->r-it->l+1)*it->val;
ans%=p;
}
return ans;
}
vector<Node>a;
inline void copy(LL l1,LL r1,LL l2,LL r2){
a.clear();
LL cnt=0;
Sit itr=split(r1+1),itl=split(l1);
for(Sit it=itl;it!=itr;it++){
a.push_back(Node(l2+it->l-l1,l2+it->r-l1,it->val));
cnt++;
}
for(LL i=0;i<cnt;i++){
assign(a[i].l,a[i].r,a[i].val);
}
}
inline void change(LL l1,LL r1,LL l2,LL r2){
copy(l1,r1,n+1,n+r1-l1+1);
copy(l2,r2,l1,r1);
copy(n+1,n+r1-l1+1,l2,r2);
}
vector<Node>v;
inline void reserve(LL l,LL r){
v.clear();
Sit itr=split(r+1),itl=split(l);
for(Sit it=itl;it!=itr;it++){
v.push_back(Node(it->l,it->r,it->val));
}
s.erase(itl,itr);
LL now=r;
for(LL i=0;i<v.size();i++){
s.insert(Node(now-(v[i].r-v[i].l),now,v[i].val));
now-=(v[i].r-v[i].l+1);
}
}
inline void print(){
Sit itr=split(n+1),itl=split(1);
for(Sit it=itl;it!=itr;it++){
for(LL i=1;i<=(it->r-it->l+1);i++){
printf("%lld ",it->val%p);
}
}
}
int main(void){
scanf("%lld%lld",&n,&m);
for(LL i=1;i<=n;i++){
LL qwq;
scanf("%lld",&qwq);
s.insert(Node(i,i,qwq));
}
while(m--){
LL opt,l1,r1,l2,r2,v;
scanf("%lld",&opt);
if(opt==1){
scanf("%lld%lld",&l1,&r1);
printf("%lld\n",query(l1,r1));
}
else if(opt==2){
scanf("%lld%lld%lld",&l1,&r1,&v);
assign(l1,r1,v);
}
else if(opt==3){
scanf("%lld%lld%lld",&l1,&r1,&v);
add(l1,r1,v);
}
else if(opt==4){
scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
copy(l1,r1,l2,r2);
}
else if(opt==5){
scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2);
change(l1,r1,l2,r2);
}
else if(opt==6){
scanf("%lld%lld",&l1,&r1);
reserve(l1,r1);
}
}
print();
return 0;
}