卿學姐與基本法（線段樹+區間更新）

時間 2020-03-25 標籤卿學姐基本法線段樹區間更新

卿學姐與基本法

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

「作專題也要按照基本法」——蛤node

離開了詭異的村莊，卿學姐來到了威廉·聖·亂七八糟王國，這裏的國王鹹魚王是個智障。ios

國家渙散，盜賊四起，民不聊生。學習

見到這樣的景象，卿學姐不由潸然淚下，「悠悠蒼天，奈何苦了蒼生」。ui

自幼學習基本法的卿學姐決定向整個國家普及基本法，改善國家法度。spa

在這個國家總共有N我的，每一個人都有一個編號，編號從1開始。code

因爲整個國家的人實在是太多了，卿學姐每次只能對一個連續區間的編號的人普及基本法。orm

同時卿學姐還想知道在某個時刻某個區間還有多少人沒有被普及基本法。blog

Input

第一行兩個整數N,Q，表示總共有N我的，而且有Q次事件。事件

接下來Q行，每行三個整數t,L,R。若是t是1，表明在這時，卿學姐向閉區間L,R的人普及基本法。若是t是2，表明在這時，卿學姐想知道閉區間L,R裏面有多少人尚未被普及基本法。ci

1≤N≤100000000

1≤Q≤100000

1≤t≤2

1≤L≤R≤N

Output

輸出每一個卿學姐想知道的答案

Sample input and output

Sample Input	Sample Output
5 3 1 1 2 1 4 5 2 2 4	1

Source

2016 UESTC Training for Data Structures

思路：

這題一直WA，用了好多個線段樹的姿式仍是過不了第七個樣例。以後看了看發下來的題解發現，根本就是一開始思路想錯了，之後的實現就變得很是的

複雜，作了好幾天也沒能A掉。以後發現其實區間的更新都是固定了值的，因此與那些單點更新區間更新存在着很大的不一樣，因此我只要將要減去的值來作

就OK了，一開始只想到加，而沒想到其實這道題目用減法更容易。

AC代碼：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
using namespace std;
#define lson (rt<<1)
#define rson (rt<<1|1)
#define T 100000 + 50
#define inf 0x3f3f3f3f
typedef long long ll;

int n,m,x[(T<<2)],sz;
struct line
{
	int f,L,R;
}le[T];

struct node
{
	int L,R,mid;
	int lazy,sum;
}tree[(T<<8)];

void Push_Up(int rt)
{
	tree[rt].sum = tree[lson].sum + tree[rson].sum;
}

void Push_Down(int rt)
{
	if(tree[rt].lazy){
		tree[lson].sum = 0;
		tree[rson].sum = 0;
		tree[lson].lazy = 1;
		tree[rson].lazy = 1;
		tree[rt].lazy = 0;
	}
}

void Build(int rt,int L,int R)//由於區間值已經所有肯定了，因此所有賦值
{
	tree[rt].L = L,tree[rt].R = R;
	tree[rt].mid = (L+R)>>1;
	tree[rt].lazy = tree[rt].sum = 0;
	if(L==R){
		tree[rt].sum = x[L]-x[L-1];//左閉右開區間的值
		return;
	}
	Build(lson,L,tree[rt].mid);
	Build(rson,tree[rt].mid+1,R);
	Push_Up(rt);
}

void Update(int rt,int L,int R)//將符合的區間的值賦值爲0
{
	if(L<=tree[rt].L&&tree[rt].R<=R){
		tree[rt].sum = 0;
		tree[rt].lazy = 1;
		return;
	}
	Push_Down(rt);
	if(R<=tree[rt].mid){
		Update(lson,L,R);
	}
	else if(L>tree[rt].mid){
		Update(rson,L,R);
	}
	else {
		Update(lson,L,tree[rt].mid);
		Update(rson,tree[rt].mid+1,R);
	}
	Push_Up(rt);
}

int query(int rt,int L,int R)
{
	if(L<=tree[rt].L&&tree[rt].R<=R){
		return tree[rt].sum;
	}
	Push_Down(rt);
	if(R<=tree[rt].mid){
		return query(lson,L,R);
	}
	else if(L>tree[rt].mid){
		return query(rson,L,R);
	}
	else {
		return query(lson,L,tree[rt].mid)+query(rson,tree[rt].mid+1,R);
	}
}

int main()
{
#ifdef zsc
	freopen("input.txt","r",stdin);
#endif

	int i,j,k;
	while(~scanf("%d%d",&n,&m))
	{
		sz = 0;
		for(i=0;i<m;++i){
			scanf("%d%d%d",&le[i].f,&le[i].L,&le[i].R);
			x[sz++] = le[i].L,x[sz++] = le[i].R;
			//if(le[i].L!=1)x[sz++]=le[i].L-1;
			x[sz++] = le[i].R+1;//爲了使區間左邊是閉合的
		}
		x[sz++] = n+1;//因爲是左閉右開區間，因此要添加一個最大的值加一
		sort(x,x+sz);
		sz=unique(x,x+sz)-x;
		Build(1,1,sz);
		for(i=0;i<m;++i){
			int L = lower_bound(x,x+sz,le[i].L)-x+1,
				R = lower_bound(x,x+sz,le[i].R)-x+1;
			if(le[i].f==1){
				Update(1,L,R);
			}
			else {
				printf("%d\n",query(1,L,R));
			}
		}
	}
	
	return 0;
}