TLE#16 ODT 求条
查看原帖
TLE#16 ODT 求条
322792
Alea楼主2023/11/10 14:47
#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast")
using namespace std;
const int SIZE=3e5+10;
int n,q,ans=0;
struct nodt{
    int lf,rt;
    mutable int val;
    nodt(int lf,int rt=-1,int val=0):lf(lf),rt(rt),val(val){}
    bool operator<(const nodt &rhs)const{
        return lf<rhs.lf;
    }
};
set<nodt> wtf;
typedef set<nodt>::iterator iter;
iter split(int pos){
    iter it=wtf.lower_bound(nodt(pos));
    if(it!=wtf.end()&&it->lf==pos) return it;
    --it;
    int lf=it->lf,rt=it->rt,val=it->val;
    wtf.erase(it);
    wtf.insert(nodt(lf,pos-1,val));
    return wtf.insert(nodt(pos,rt,val)).first;
}
void assign(int lf,int rt,int val){
    iter itr=split(rt+1),itl=split(lf);
    for(iter it=itl;it!=itr;++it) ans-=(it->val/2)*(it->rt-it->lf+1);
    wtf.erase(itl,itr);
    wtf.insert(nodt(lf,rt,val));
    ans+=(rt-lf+1)*(val/2);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    wtf.insert(nodt(1,n,2));
    ans=n;
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        assign(l,r,k);
        cout<<ans<<endl;
    }
    return 0;
}
2023/11/10 14:47
加载中...