【LOJ#10115,tyvj1473】校门外的树（第3次升级）

PS：思路来源于Clove_unique的博客，在此万分感谢

这道题可以用树状数组轻松过，然而...树状数组不太熟悉，还是用线段树比较好（虽然代码比较长）

【思路分析】

【一开始的思路】

最开始的错误想法：当作一般的区间覆盖题来做（顺便吐槽了一波这题太睿（ruo）智了），但写到一半突然发现，真正睿智的人是我...因为直接做的话，同一种树程序会当做不同的树来做，直接无脑相加导致答案偏大

【正确的思路】

（来自于Clove_unique）

我们额外再开一个数组P，用来记录某次更新时，如果某个节点左右两个区间都要更新的话，P数组把重复的情况记下来，最后求query的时候减掉P[该节点]；

P.S.：P数组更新有很多种情况，最好可以在草稿纸上模拟一棵线段树，手动算一下

接下来的，就见代码吧

#include<iostream>

#include<cstdio>

#include<algorithm>

#define M (int)5e4

using namespace std;

inline int read(){

	char chr = getchar();	int f = 1,ans = 0;

	while(!isdigit(chr)) {if(chr == '-') f = -1;chr = getchar();}

	while(isdigit(chr))  {ans = (ans << 3) + (ans << 1);ans += chr - '0';chr = getchar();}

	return ans* f ;

}

void write(int x){

	if(x < 0) putchar('-'),x = -x;

	if(x > 9) write(x / 10);

	putchar(x % 10 + '0');

}

struct node{

	int sum,lazy;

}t[M<<2];

int p[M<<2];

void push_up(int i){

	t[i].sum=t[i<<1].sum+t[i<<1|1].sum-p[i];

}

void push_down(int i){

	if(t[i].lazy==0) return;

	p[i<<1]+=t[i].lazy;//普通的打lazy_tag就不说了，这里但是P数组不能忘记加上去

	p[i<<1|1]+=t[i].lazy;

	t[i<<1].sum+=t[i].lazy;

	t[i<<1].lazy+=t[i].lazy;

	t[i<<1|1].sum+=t[i].lazy;

	t[i<<1|1].lazy+=t[i].lazy;

	t[i].lazy=0;

}

int query(int i,int ql,int qr,int l,int r){

	if(ql<=l&&r<=qr)	return t[i].sum;

	int m=l+r>>1;

	push_down(i) ;//下传

	int a=0,b=0;

	bool ba=0,bb=0;//记录左右儿子有没有更新过

	if(m>=ql) ba=1,a=query(i<<1,ql,qr,l,m);

	if(m<qr)  bb=1,b=query(i<<1|1,ql,qr,m+1,r);

	push_up(i);//上传

	if(ba&&bb)

		return a+b-p[i];//如果左右两个节点都更新过了，那么要减掉P的值

	return a+b;

}

void updata(int i,int ql,int qr,int l,int r,int v){

	if(ql<=l&&r<=qr){

		t[i].sum+=v;

		t[i].lazy+=v;

		p[i]+=v;//戳重点

		return;

	}

	push_down(i);

	int m=l+r>>1;

	bool ba=0,bb=0;

	if(ql<=m) ba=1,updata(i<<1,ql,qr,l,m,v);

	if(qr>m)  bb=1,updata(i<<1|1,ql,qr,m+1,r,v);

	if(ba&&bb) p[i]+=v;//更新时，左右儿子都更新过的话，P也要更新

	push_up(i);

}

int n,m,x,y;

int main(){

	n=read(),m=read();

	for(int i=1;i<=m;i++){

		int opt=read(),x=read(),y=read();

		if(opt==1)

			updata(1,x,y,1,M,1);

		else

			write(query(1,x,y,1,M)),puts("");

	}

	return 0;

}

巴特西

【LOJ#10115,tyvj1473】校门外的树（第3次升级）

PS：思路来源于Clove_unique的博客，在此万分感谢

【思路分析】

【一开始的思路】

最开始的错误想法：当作一般的区间覆盖题来做（顺便吐槽了一波这题太睿（ruo）智了），但写到一半突然发现，真正睿智的人是我...因为直接做的话，同一种树程序会当做不同的树来做，直接无脑相加导致答案偏大

【正确的思路】

我们额外再开一个数组P，用来记录某次更新时，如果某个节点左右两个区间都要更新的话，P数组把重复的情况记下来，最后求query的时候减掉P[该节点]；

最新文章

热门文章