codeforces 915E - Physical Education Lessons 动态开点线段树

题意:

最大$10^9$的区间,

$3*10^5$次区间修改,每次操作后求整个区间的和

题解:

裸的动态开点线段树,计算清楚数据范围是关键...

经过尝试

最终$1.5*10^7$的$vector$/数组可以过

#include <bits/stdc++.h>

#define endl '\n'

#define ll long long

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)

using namespace std;

int casn,n,m,k;

const int maxn=1e7+5e6+7;

class dsegtree{public:

#define nd  node[now]

#define ndl node[node[now].son[0]]

#define ndr node[node[now].son[1]]

    struct dsegnode {

        int son[2],tag,sum;

        dsegnode(){}

        dsegnode(int s,int t){sum=t-s+1,tag=son[0]=son[1]=0;}

        void update(int x,int len){sum=len*(x-1),tag=x;}

    };

    vector<dsegnode> node;

	int root,cnt,n,s,t;

    dsegtree(int nn,int size=maxn){

    	n=nn;

    	node.resize(maxn);

    	node[1]=dsegnode(1,n);

    	cnt=root=1;

	}

    void pushup(int now){nd.sum=ndl.sum+ndr.sum;}

    void pushdown(int now,int s,int t){

		if(nd.tag){

			ndl.update(nd.tag,(t+s)/2-s+1);

			ndr.update(nd.tag,t-((t+s)/2+1)+1);

			nd.tag=0;

		}

    }

    void update(int ss,int tt,int x){s=ss,t=tt,update(1,n,x,root);}

    void update(int l,int r,int x,int now){

    	if(s>r||t<l)return ;

    	if(s<=l&&t>=r) {

			nd.update(x,r-l+1);

			return ;

    	}

    	if(!nd.son[0]){

			node[++cnt]=dsegnode(l,(l+r)>>1);

			nd.son[0]=cnt;

    	}

    	if(!nd.son[1]){

			node[++cnt]=dsegnode(((l+r)>>1)+1,r);

			nd.son[1]=cnt;

    	}

    	pushdown(now,l,r);

		update(l,(l+r)>>1,x,nd.son[0]);

		update(((l+r)>>1)+1,r,x,nd.son[1]);

    	pushup(now);

    }

};

int main() {

	IO;

	ll n,m;

	cin>>n>>m;

	dsegtree tree(n);

	int a,b,c;

	while(m--){

		cin>>a>>b>>c;

		tree.update(a,b,c);

		cout<<tree.node[tree.root].sum<<endl;

	}

	return 0;

}

91

题解5