珂朵莉树求助
  • 板块学术版
  • 楼主rand_Zq
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/29 21:57
  • 上次更新2024/8/30 10:28:45
查看原帖
珂朵莉树求助
901086
rand_Zq楼主2024/8/29 21:57

P5350 序列

悬10r 但是要我理解了为什么是错的

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5,mod=1e9+7;
struct chtholly{
    struct node{
        mutable int l,r,num;
        friend int operator<(node x,node y){
            return x.l<y.l;
        }
    };
    set<node>S;
    void insert(int pos,int x){
        S.insert({pos,pos,x});
    }
    void print(){
        for(auto [l,r,num]:S){
            for(int i=l;i<=r;i++){
                cout<<num<<" ";
            }
        }
        cout<<'\n';
    }
    set<node>::iterator split(int x){
        auto pos=S.lower_bound({x,0,0});
        if(pos!=S.end()&&(*pos).l==x){
            return pos;
        }
        pos--;
        auto [l,r,num]=(*pos);
        S.erase(pos),S.insert({l,x-1,num}),S.insert({x,r,num});
        return S.find({x,r,num});
    }
    int sum(int l,int r){
        auto A=split(r+1),B=split(l);
        int ret=0;
        while(B!=A){
            ret=(ret+(*B).num*((*B).r-(*B).l+1))%mod,B++;
        }
        return ret;
    }
    void assign(int l,int r,int val){
        auto A=split(r+1),B=split(l);
        S.erase(B,A),S.insert({l,r,val});
    }
    void add(int l,int r,int val){
        auto A=split(r+1),B=split(l);
        while(B!=A){
            (*B).num=((*B).num+val)%mod,B++;
        }
    }
    void copy(int l1,int r1,int l2,int r2){
        auto A1=split(r1+1),B1=split(l1),A2=split(r2+1),B2=split(l2);
        S.erase(B2,A2);
        vector<node>add;
        while(B1!=A1){
            add.push_back({l2,l2+(*B1).r-(*B1).l,(*B1).num}),l2+=(*B1).r-(*B1).l+1,B1++;
        }
        for(auto i:add){
            S.insert(i);
        }
    }
    void swap(int l1,int r1,int l2,int r2){
        vector<node>add,del;
        auto A1=split(r1+1),B1=split(l1),A2=split(r2+1),B2=split(l2);
        while(B1!=A1){
            del.push_back(*B1),add.push_back({l2,l2+(*B1).r-(*B1).l,(*B1).num}),l2+=(*B1).r-(*B1).l+1,B1++;
        }
        while(B2!=A2){
            del.push_back(*B2),add.push_back({l1,l1+(*B2).r-(*B2).l,(*B2).num}),l1+=(*B2).r-(*B2).l+1,B2++;
        }
        for(auto i:del){
            S.erase(S.find(i));
        }
        for(auto i:add){
            S.insert(i);
        }
    }
    void reverse(int l,int r){
        auto A=split(r+1),B=split(l);
        vector<node>vec;
        while(B!=A){
            vec.push_back(*B),B++;
        }
        B=split(l),S.erase(B,A),std::reverse(vec.begin(),vec.end());
        for(auto i:vec){
            S.insert({l,l+i.r-i.l,i.num}),l+=i.r-i.l+1;
        }
    }
}tree;
int n,T;
signed main(){
    cin>>n>>T;
    for(int i=1,x;i<=n;i++){
        cin>>x,tree.insert(i,x);
    }
    for(int typ,l1,r1,l2,r2;T--;){
        cin>>typ>>l1>>r1;
        if(typ==1){
            cout<<tree.sum(l1,r1)<<'\n';
        }
        if(typ==2){
            cin>>l2,tree.assign(l1,r1,l2);
        }
        if(typ==3){
            cin>>l2,tree.add(l1,r1,l2);
        }
        if(typ==4){
            cin>>l2>>r2,tree.copy(l1,r1,l2,r2);
        }
        if(typ==5){
            cin>>l2>>r2,tree.swap(l1,r1,l2,r2);
        }
        if(typ==6){
            tree.reverse(l1,r1);
        }
    }
    tree.print();
}
2024/8/29 21:57
加载中...