线段树 完全版

时间:2021-09-19 16:17:12
以下均来自神牛的杰作,可作为参考:

关于线段树的功能基本都在下面阐述,衷心感谢



单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来

Hdu1754 I hate it

线段树功能:update:单点替换 query:区间最值



#include<iostream>

#include<algorithm>

using namespace std;

int MAXN[4000001],d[4000001];

void PushUp(int rt)

{
	
	MAXN[rt]=max(MAXN[rt<<1],MAXN[rt<<1|1]);
	
}

void build(int l,int r,int rt)

{
	
	if(l==r)
		
	{
		
		cin>> MAXN[rt];
		
		return;
		
	}
	
	int m=(l+r)>>1;
	
	build(l,m,rt<<1);
	
	build(m+1,r,(rt<<1)+1);
	
	PushUp(rt);
	
}

void update(int p,int sc,int l,int r,int rt)

{
	
    if(l==r)
		
	{
		
		MAXN[rt]=sc;
		
		return;
		
	}
	
	int m=(l+r)>>1;
	
	if(p<=m)update(p,sc,l,m,rt<<1);
	
	else update(p,sc,m+1,r,(rt<<1)+1);
	
	PushUp(rt);
	
}

int getmax(int L,int R,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)
		
	{
		
		return MAXN[rt];
		
	}
	
	int m=(l+r)>>1;
	
	int ret=0;
	
	if(L<=m)ret=max(ret,getmax(L,R,l,m,rt<<1));
	
	if(R>m)ret=max(ret,getmax(L,R,m+1,r,(rt<<1)+1));
	
	return ret;
	
}

int main()

{
	
	int n,m,a,b;
	
	char ch;
	
	while(cin>>n>>m)
		
	{
		
		build(1,n,1);
		
		for(int i=0;i<m;i++)
			
		{
			
			cin>>ch>>a>>b;
			
			if(ch=='U')update(a,b,1,n,1);
			
			else cout<<getmax(a,b,1,n,1)<<endl;
			
		}
		
	}
	
}

hdu1166敌兵布阵

线段树功能:update:单点增减 query:区间求和



#include<iostream>

#include<string>

using namespace std;

const int maxn=55555;

int sum[maxn<<2];

void PushUp(int rt)

{
	
    sum[rt]=sum[rt<<1]+sum[(rt<<1)+1];
	
}

void build(int l,int r,int rt)

{
	
    if(l==r)
		
    {
		
		cin>>sum[rt];
		
		return;
		
    }
	
    int m=(l+r)>>1;
	
    build(l,m,rt<<1);
	
    build(m+1,r,(rt<<1)+1);
	
    PushUp(rt);
	
}

void update(int p,int add,int l,int r,int rt)

{
	
	if(l==r)
		
	{
		
		sum[rt]+=add;
		
		return;
		
	}
	
	int m=(l+r)>>1;
	
	if(p<=m)update(p,add,l,m,rt<<1);
	
	else update(p,add,m+1,r,(rt<<1)+1);
	
	PushUp(rt);
	
}

int getsum(int L,int R,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)
		
    {
		
        return sum[rt];
		
    }
	
    int m=(r+l)>>1;
	
    int ret=0;
	
    if(L<=m)ret+=getsum(L,R,l,m,rt<<1);
	
    if(R>m)ret+=getsum(L,R,m+1,r,(rt<<1)+1);
	
    return ret;
	
}

int main()

{
	
    int cas,n,a,b,k=0;
	
    string s;
	
    cin>>cas;
	
    while(cas--)
		
    {
		
        k++;
		
        cout<<"Case "<<k<<":"<<endl;
		
        cin>>n;
		
        build(1,n,1);
		
        while(cin>>s)
			
        {
			
            if(s=="End")break;
			
            if(s=="Query")
				
            {
				
                cin>>a>>b;
				
                cout<<getsum(a,b,1,n,1)<<endl;
				
            }
			
            else if(s=="Add")
				
            {
				
                cin>>a>>b;
				
                update(a,b,1,n,1);
				
            }
			
            else 
				
            {
				
                cin>>a>>b;
				
                update(a,-b,1,n,1);
				
            }
			
        }
		
    }
	
}



hdu1394 Minimum Inversion Number
题意:求Inversion后的最小逆序数
思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解
线段树功能:update:单点增减 query:区间求和



#include<iostream>

#include<algorithm>

using namespace std;

int sum[10001],x[5001];

void PushUp(int rt)

{
	
	sum[rt]=sum[rt<<1]+sum[(rt<<1)+1];
	
}

void build(int l,int r,int rt)

{
	
	sum[rt]=0;
	
	if(l==r)return;
	
    int m=(l+r)>>1;
	
	build(l,m,rt<<1);
	
	build(m+1,r,(rt<<1)+1);
	
}

void update(int p,int l,int r,int rt)

{
	
	if(l==r)
		
	{
		
		sum[rt]++;return;
		
	}
	
	int m=(l+r)>>1;
	
	if(p<=m)update(p,l,m,rt<<1);
	
	else update(p,m+1,r,(rt<<1)+1);
	
	PushUp(rt);
	
}

int GetReverse(int L,int R,int l,int r,int rt)

{
	
	if(L<=l&&r<=R)return sum[rt];
	
	int m=(l+r)>>1;
	
	int ret=0;
	
	if(L<=m)ret+=GetReverse(L,R,l,m,rt<<1);
	
	if(R>m)ret+=GetReverse(L,R,m+1,r,(rt<<1)+1);
	
	return ret;
	
}

int main()

{
	
	int n;
	
	while(cin>>n)
		
	{
		
		build(0,n-1,1);
		
		int sum=0;
		
		for(int i=0;i<n;i++)
			
		{
			
			cin>>x[i];
			
			sum+=GetReverse(x[i],n-1,0,n-1,1);//求x[i]到n-1之间已存在几个数字,即求x[i]的逆序数
			
			update(x[i],0,n-1,1);//包含[x[i],x[i]]的区间+1
			
		}
		
		int ret=sum;
		
		for(int i=0;i<n;i++)
			
		{//把第一个位子上的数(x[i])移到最后,则被移的数的逆序是n-1-x[i],而未被移的数字有x[i]个比x[i]小
			
			sum+=n-1-x[i]-x[i];
			
			ret=min(sum,ret);
			
		}
		
		cout<<ret<<endl;
		
	}
	
}

hdu2795Billboard

题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
思路:每次找到最大值的位子,然后减去L
线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)



#include<iostream>

#include<algorithm>

using namespace std;

int MAX[222222<<2];

int w;

void PushUp(int rt)

{
	
	MAX[rt]=max(MAX[rt<<1],MAX[(rt<<1)|1]);
	
}

void build(int l,int r,int rt)

{
	
    MAX[rt]=w;//c初始化 每行都有W的空间
	
    if(l==r)return;
	
    int m=(l+r)>>1;
	
    build(l,m,rt<<1);
	
    build(m+1,r,(rt<<1|1));
	
}

int query(int x,int l,int r,int rt)

{
	
    if(l==r){MAX[rt]-=x;return l;}
	
    int m=(l+r)>>1;
	
    int ret=(MAX[rt<<1] >= x? query(x ,l,m,rt<<1):query(x ,m+1,r,(rt<<1)|1)) ;//查找左边能放得下,优先左边
	
    PushUp(rt);
	
    return ret;
	
}

int main()

{
	
    int h,n,x;
	
    while(scanf("%d%d%d",&h,&w,&n)==3)
		
    {
		
        if(h>n)h=n;//题目中h>1,n<200000,h可能会大于所开的MAX[];
		
        build(1,h,1);
		
		for(int i=0;i<n;i++)
			
		{
			
            scanf("%d",&x);
			
			if(x>MAX[1])printf("%d\n",-1);
			
			else printf("%d\n",query(x,1,h,1));
			
		}
		
    }
	
}

成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候 

hdu1698Just a Hook
题意:O(-1)
思路:O(-1)
线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息)
				   
				   
				   
#include <cstdio>
				   
#include <algorithm>
				   
 using namespace std;

const int maxn = 111111;

int col[maxn<<2];

int sum[maxn<<2];

void PushUp(int rt)

{
	
    sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];
	
}

void PushDown(int rt,int m)

{
	
	if(col[rt])
		
	{
		
		col[(rt<<1)|1]=col[rt<<1]=col[rt];        
		
		sum[rt<<1]=col[rt]*(m-(m>>1));
		
		sum[(rt<<1)|1]=col[rt]*(m>>1);
		
		col[rt]=0;
		
	}
	
}

void build(int l,int r,int rt)

{
	
    col[rt]=0;sum[rt]=1;
	
    if(l==r)return;
	
    int m=(l+r)>>1;
	
    build(l,m,rt<<1);
	
    build(m+1,r,(rt<<1)|1);
	
    PushUp(rt);
	
}

void update(int L,int R,int c,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)
		
    {
		
        col[rt]=c;
		
        sum[rt]=(r-l+1)*c;
		
        return;
		
    }
	
    PushDown(rt,r-l+1);
	
    int m=(l+r)>>1;
	
    if(L<=m)update(L,R,c,l,m,rt<<1);
	
    if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);
	
    PushUp(rt);
	
}

int main()

{
	
    int cas,n,m,a,b,c,k=0;
	
    scanf("%d",&cas);
	
    while(cas--)
		
    {
		
        k++;
		
        scanf("%d",&n);
		
        build(1,n,1);
		
        scanf("%d",&m);
		
        while(m--)
			
        {
			
			scanf("%d%d%d",&a,&b,&c);
			
			update(a,b,c,1,n,1);
			
        }
		
        printf("Case %d: The total value of the hook is %d.\n",k,sum[1]);
		
    }
	
}

3468A Simple Problem with Integers
线段树功能:update:成段增减 query:区间求和



#include<iostream>

#include <algorithm>

using namespace std;

const int maxn = 111111;

long long int add[maxn<<2];

long long int sum[maxn<<2];

void PushUp(int rt)

{
	
	sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];
	
}

void PushDown(int rt,int m)

{
	
	if(add[rt])
		
	{
		
		add[rt<<1]+=add[rt];
		
		add[(rt<<1)|1]+=add[rt]; 
		
		sum[rt<<1]+=add[rt]*(m-(m>>1));
		
		sum[(rt<<1)|1]+=add[rt]*(m>>1);
		
		add[rt]=0;
		
	}
	
}

void build(int l,int r,int rt)

{
	
	add[rt]=0;
	
	if(l==r)
		
	{
		
		cin>>sum[rt];
		
		return;
		
	}
	
    int m=(l+r)>>1;
	
	build(l,m,rt<<1);
	
	build(m+1,r,(rt<<1)|1);
	
	PushUp(rt);
	
}

void update(int L,int R,int c,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)
		
	{
		
		add[rt]+=c;
		
		sum[rt]+=(long long int)(r-l+1)*c;
		
		return;
		
	}
	
	PushDown(rt,r-l+1);
	
	int m=(l+r)>>1;
	
	if(L<=m)update(L,R,c,l,m,rt<<1);
	
	if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);
	
	PushUp(rt);
	
}

long long int query(int L,int R,int l,int r,int rt)

{
	
	if(L<=l&&r<=R)return sum[rt];
	
	PushDown(rt,r-l+1);
	
	int m=(l+r)>>1;
	
	long long int ret=0;
	
	if(L<=m)ret+=query(L,R,l,m,rt<<1);
	
	if(m<R)ret+=query(L,R,m+1,r,(rt<<1)|1);
	
	return ret;
	
}

int main()

{
	
	int n,m,a,b,c;
	
	char ch;
	
	while(cin>>n>>m)
		
	{
		
		build(1,n,1);
		
		for(int i=0;i<m;i++)
			
		{
			
			cin>>ch;
			
			if(ch=='C')
				
			{
				
				cin>>a>>b>>c;
				
				update(a,b,c,1,n,1);
				
			}
			
			else {cin>>a>>b;cout<<query(a,b,1,n,1)<<endl;}
			
		}
		
	}
	
}

poj2528Mayor's posters

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
给出下面两个简单的例子应该能体现普通离散化的缺陷:
1-10 1-4 5-10
1-10 1-4 6-10
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
线段树功能:update:成段替换 query:简单hash



#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn=11111;

int col[maxn<<4],le[maxn],ri[maxn],X[maxn*3],hash[maxn];

int ans;

void PushDown(int rt)

{
	
	if(col[rt]!=-1)
		
	{
		
        col[rt<<1]=col[(rt<<1)|1]=col[rt];
		
		col[rt]=-1;
		
	}
	
}

void update(int L,int R,int c,int l,int r,int rt)

{
	
	if(L<=l&&r<=R)
		
	{
		
		col[rt]=c;
		
		return;
		
	}
	
	PushDown(rt);
	
	int m=(l+r)>>1;
	
	if(L<=m)update(L,R,c,l,m,rt<<1);
	
	if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);
	
}

void query(int l,int r,int rt)

{
	
	if(col[rt]!=-1)
		
	{
		
		if(!hash[col[rt]]){ans++;hash[col[rt]]=1;}
		
		return;
		
	}
	
	if(l==r)return;
	
	int m=(l+r)>>1;
	
	query(l,m,rt<<1);
	
	query(m+1,r,(rt<<1)|1);
	
}

int Bin(int key,int n)

{
	
    int l=0,r=n-1; 
	
	while(l<=r)
		
	{
		
        int m=(l+r)>>1;
		
		if(X[m]==key)return m;
		
		if(X[m]>key) r=m-1;
		
		else l=m+1;
		
	}
	
	return -1;
	
}

int main()

{
	
    int cas,n;
	
	cin>>cas;
	
	while(cas--)
		
	{
		
		cin>>n;
		
		int nn=0;
		
		for(int i=0;i<n;i++)
			
		{
			
			cin>>le[i]>>ri[i];
			
			X[nn++]=le[i],X[nn++]=ri[i];
			
		}
		
		sort(X,X+nn);
		
		int m=1;
		
		for(int i=1;i<nn;i++)if(X[i]!=X[i-1])X[m++]=X[i];
		
		for(int i=m-1;i>0;i--)if(X[i]!=X[i-1]+1)X[m++]=X[i-1]+1;
		
		sort(X,X+m);
		
		
		
		memset(col,-1,sizeof(col));
		
		for(int i=0;i<n;i++)
			
		{
			
			int l=Bin(le[i],m);
			
			int r=Bin(ri[i],m);
			
			update(l,r,i,0,m,1);
			
		}
		
		ans=0;
		
		memset(hash,0,sizeof(hash));
		
		
		
		query(0,m,1);
		
		cout<<ans<<endl;
		
	}
	
}

区间合并这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并 

poj3667Hotel
题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空
思路:记录区间中最长的空房间
线段树操作:update:区间替换 query:询问满足条件的最左断点



#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=50000;

int cover[maxn<<2];

int lsum[maxn<<2],rsum[maxn<<2],msum[maxn<<2];

void PushUp(int rt,int m)

{
	
	lsum[rt]=lsum[rt<<1],rsum[rt]=rsum[(rt<<1)|1];
	
	if(lsum[rt<<1]==m-(m>>1))lsum[rt]+=lsum[(rt<<1)|1];
	
	if(rsum[(rt<<1)|1]==m>>1)rsum[rt]+=rsum[rt<<1];
	
	msum[rt]=max(max(msum[rt<<1],msum[(rt<<1)|1]),rsum[rt<<1]+lsum[(rt<<1)|1]);
	
}

void PushDown(int rt,int m)

{
	
	if(cover[rt]!=-1)
		
	{
		
		cover[rt<<1]=cover[(rt<<1)|1]=cover[rt];
		
		lsum[rt<<1]=rsum[rt<<1]=msum[rt<<1]=(cover[rt]? 0:m-(m>>1));
		
		lsum[(rt<<1)|1]=rsum[(rt<<1)|1]=msum[(rt<<1)|1]=(cover[rt]? 0:m>>1);
		
		cover[rt]=-1;
		
	}
	
}

void build(int l,int r,int rt)

{
	
	cover[rt]=-1;
	
	lsum[rt]=rsum[rt]=msum[rt]=r-l+1;
	
	if(l==r)return;
	
	int m=(l+r)>>1;
	
	build(l,m,rt<<1);
	
	build(m+1,r,(rt<<1)|1);
	
}

void update(int L,int R,int c,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)
		
	{
		
		cover[rt]=c;
		
		lsum[rt]=rsum[rt]=msum[rt]=(c? 0:r-l+1);
		
		return;
		
	}
	
	PushDown(rt,r-l+1);
	
	int m=(l+r)>>1;
	
	if(L<=m)update(L,R,c,l,m,rt<<1);
	
	if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);
	
	PushUp(rt,r-l+1);
	
}

int query(int w,int l,int r,int rt)

{
	
    if(l==r)return l;
	
	PushDown(rt,r-l+1);
	
	int m=(l+r)>>1;
	
	if(msum[rt<<1]>=w)return query(w,l,m,rt<<1);
	
	else if(rsum[rt<<1]+lsum[(rt<<1)|1]>=w)return m-rsum[rt<<1]+1;
	
	else query(w,m+1,r,(rt<<1)|1);
	
}

int main()

{
	
	int n,m,a,b,c;
	
	while(cin>>n>>m)
		
	{
		
		build(1,n,1);
		
		while(m--)
			
		{
			
			cin>>a;
			
			if(a==1)
				
			{
				
				cin>>b;
				
				if(msum[1]<b){cout<<0<<endl;continue;}
				
				int ans=query(b,1,n,1);
				
				cout<<ans<<endl;
				
				update(ans,ans+b-1,1,1,n,1);
				
			}
			
			else 
				
			{
				
				cin>>b>>c;
				
				update(b,b+c-1,0,1,n,1);
				
			}
			
		}
		
	}
	
}

hdu3911Black And White

题意:给出01串 1代表黑色 0代表白色

0 a b:询问[a,b]中1的连续最大长度

1 a,b:把[a,b]区间的0->1 1->0

思路:lsum1[],rsum1[],msum1[]分别表示区间做起连续1的最大长度,右起连续1的最大长度,区间1的最大连续长度

lsum0[],rsum0[],msum0[]分别表示区间做起连续0的最大长度,右起连续0的最大长度,区间连续0的最大连续长度

0 a b:交换 0和1的lsum[] rsum[] msum[]; ROX[]表示需要向儿子更新 两次更新=不变

线段树功能:update区间替换,query询问区间1的最大连续长度



#include<iostream>

#include<stdio.h>

#include<algorithm>

using namespace std;

const int maxn=100001;

int ROX[maxn<<2];

int lsum1[maxn<<2],rsum1[maxn<<2],msum1[maxn<<2];

int lsum0[maxn<<2],rsum0[maxn<<2],msum0[maxn<<2];

void PushUp(int rt,int m)

{
	
    lsum1[rt]=lsum1[rt<<1],rsum1[rt]=rsum1[(rt<<1)|1];
	
    if(lsum1[rt<<1]==m-(m>>1))lsum1[rt]+=lsum1[(rt<<1)|1];
	
    if(rsum1[(rt<<1)|1]==m>>1)rsum1[rt]+=rsum1[rt<<1];
	
    msum1[rt]=max(max(msum1[rt<<1],msum1[(rt<<1)|1]),rsum1[rt<<1]+lsum1[(rt<<1)|1]);
	
    lsum0[rt]=lsum0[rt<<1],rsum0[rt]=rsum0[(rt<<1)|1];
	
    if(lsum0[rt<<1]==m-(m>>1))lsum0[rt]+=lsum0[(rt<<1)|1];
	
    if(rsum0[(rt<<1)|1]==m>>1)rsum0[rt]+=rsum0[rt<<1];
	
    msum0[rt]=max(max(msum0[rt<<1],msum0[(rt<<1)|1]),rsum0[rt<<1]+lsum0[(rt<<1)|1]);
	
}

void PushDown(int rt,int m)

{
	
    if(ROX[rt])
		
    {
		
        ROX[rt<<1]^=1,ROX[(rt<<1)|1]^=1;
		
        swap(lsum0[rt<<1],lsum1[rt<<1]),swap(rsum1[rt<<1],rsum0[rt<<1]),swap(msum1[rt<<1],msum0[rt<<1]);
		
        swap(lsum0[(rt<<1)|1],lsum1[(rt<<1)|1]),  swap(rsum1[(rt<<1)|1],rsum0[(rt<<1)|1]),  swap(msum1[(rt<<1)|1],msum0[(rt<<1)|1]);
		
        ROX[rt]=0;
		
    }
	
}

void build(int l,int r,int rt)

{
	
    ROX[rt]=0;
	
    if(l==r)
		
    {
		
        int c;
		
        scanf("%d",&c);
		
        lsum1[rt]=rsum1[rt]=msum1[rt]=c;
		
        lsum0[rt]=rsum0[rt]=msum0[rt]=c^1;
		
        return;
		
    }
	
    int m=(l+r)>>1;
	
    build(l,m,rt<<1);
	
    build(m+1,r,(rt<<1)|1);
	
    PushUp(rt,r-l+1);
	
}

void update(int L,int R,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)
		
    {
		
        ROX[rt]^=1;
		
        swap(lsum0[rt],lsum1[rt]),swap(rsum1[rt],rsum0[rt]),swap(msum1[rt],msum0[rt]);
		
        return;
		
    }
	
    PushDown(rt,r-l+1);
	
    int m=(l+r)>>1;
	
    if(L<=m)update(L,R,l,m,rt<<1);
	
    if(R>m)update(L,R,m+1,r,(rt<<1)|1);
	
    PushUp(rt,r-l+1);
	
}

int query(int L,int R,int l,int r,int rt)

{
	
    if(L<=l&&r<=R)return msum1[rt];
	
    int tmp;
	
    PushDown(rt,r-l+1);
	
    int m=(l+r)>>1;
	
    if(m>=R) tmp=query(L,R,l,m,rt<<1);
	
    else if(m<L)tmp=query(L,R,m+1,r,(rt<<1)|1);
	
    else 
		
    {
		
		tmp=max(query(L,R,l,m,rt<<1),query(L,R,m+1,r,(rt<<1)|1));
		
        int tmp1=min(m-L+1,rsum1[rt<<1]);
		
        int tmp2=min(R-m,lsum1[(rt<<1)|1]);
		
        tmp=max(tmp,tmp1+tmp2);
		
    }
	
    return tmp;
	
}

int main()

{
	
    int n,m,a,b,c;
	
    while(scanf("%d",&n)==1)
		
    {
		
        build(1,n,1);
		
        scanf("%d",&m);
		
        while(m--)
			
        {
			
            scanf("%d%d%d",&a,&b,&c);
			
            if(a==1)update(b,c,1,n,1);
			
            else cout<<query(b,c,1,n,1)<<endl;
			
			
			
        }
		
    }
	
}

扫描线
这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去
最典型的就是矩形面积并,周长并等题

hdu1542Atlantis

题意:矩形面积并
思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该区间下边比上边多几个
线段树操作:update:区间增减 query:直接取根节点的值



#include<iostream>

#include<algorithm>

#include<cstring>

#include<iomanip>

using namespace std;

const int maxn=201;

int cnt[maxn<<2];

double X[maxn<<1],sum[maxn<<2];

struct Seg

{
	
	double l,r,h;
	
	int c;
	
	Seg(){};
	
	Seg(double _l,double _r,double _h,int _c):l(_l),r(_r),h(_h),c(_c){};
	
	bool operator <(const Seg& cmp)
		
	{
		
		return h<cmp.h;
		
	}
	
}s[maxn<<2];

void PushUp(int rt,int l,int r)

{
	
    if(cnt[rt])sum[rt]=X[r+1]-X[l];
	
	else if(l==r)sum[rt]=0;
	
	else sum[rt]=sum[rt<<1]+sum[(rt<<1)|1];
	
}

void update(int L,int R,int c,int l,int r,int rt)

{
	
	if(L<=l&&r<=R)
		
	{
		
        cnt[rt]+=c;
		
		PushUp(rt,l,r);
		
		return;
		
	}
	
	int m=(l+r)>>1;
	
	if(L<=m)update(L,R,c,l,m,rt<<1);
	
	if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);
	
	PushUp(rt,l,r);
	
}

int Bin(double key,int n)

{ 
	
	int l=0,r=n-1;
	
	while(l<=r)
		
	{
		
		int m=(l+r)>>1;
		
		if(X[m]==key)return m;
		
		if(key<X[m])r=m-1;
		
		else l=m+1;
		
	}
	
	return -1;
	
}

int main()

{
	
	cout.precision(2);
	
    int n,cas=0;
	
	double a,b,c,d;
	
	while(cin>>n&&n)
		
	{
		
		cas++;
		
		int m=0;
		
        for(int i=0;i<n;i++)
			
		{
			
			cin>>a>>b>>c>>d;
			
			s[m]=Seg(a,c,b,1);
			
			X[m++]=a;
			
			s[m]=Seg(a,c,d,-1);
			
			X[m++]=c;
			
		}
		
		sort(X,X+m);
		
		sort(s,s+m);
		
		int k=1;
		
		double ans=0;
		
		for(int i=1;i<m;i++)if(X[i]!=X[i-1])X[k++]=X[i];
		
		memset(cnt,0,sizeof(cnt));
		
		memset(sum,0,sizeof(sum));
		
		for(int i=0;i<m;i++)
			
		{
			
			int l=Bin(s[i].l,k);
			
			int r=Bin(s[i].r,k)-1;
			
			if (l <= r) update(l,r,s[i].c,0,k-1,1);
			
			ans+=sum[1]*(s[i+1].h-s[i].h);
			
		}
		
		cout<<"Test case #"<<cas<<endl;
		
		cout<<"Total explored area: "<<fixed<<ans<<endl; 
		
		cout<<endl;
		
	}
	
}

hdu1828Picture

题意:矩形周长并
思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用lbd和rbd表示边界来辅助)
					   线段树操作:update:区间增减 query:直接取根节点的值
					   
					   
					   
#include<iostream>
					   
#include<algorithm>
					   
#include<cmath>
					   
					   using namespace std;

const int maxn=20001;

int len[maxn<<2],lbd[maxn<<2],rbd[maxn<<2],cnt[maxn<<2],numSeg[maxn<<2];

struct Seg

{
	
	int l,r,h,c;
	
	Seg(){};
	
	Seg(int _l,int _r,int _h,int _c):l(_l),r(_r),h(_h),c(_c){};
	
	bool operator<(Seg&a)
		
	{
		
		return h<a.h;
		
	}
	
}s[maxn];

void PushUp(int rt,int l,int r)

{
	
	if(cnt[rt])
		
	{
		
		lbd[rt]=rbd[rt]=1;
		
		len[rt]=r-l+1;
		
		numSeg[rt]=2;
		
	}
	
	else if(l==r)
		
	{
		
		lbd[rt]=rbd[rt]=len[rt]=numSeg[rt]=0;
		
	}
	
	else 
		
	{
		
		lbd[rt]=lbd[rt<<1],rbd[rt]=rbd[(rt<<1)|1];
		
		len[rt]=len[rt<<1]+len[(rt<<1)|1];
		
		numSeg[rt]=numSeg[rt<<1]+numSeg[(rt<<1)|1];
		
		if(rbd[rt<<1]&&lbd[(rt<<1)|1])numSeg[rt]-=2;
		
	}
	
}

void update(int L,int R,int c,int l,int r,int rt)

{
	
	if(L<=l&&r<=R)
		
	{
		
		cnt[rt]+=c;
		
		PushUp(rt,l,r);
		
		return;
		
	}
	
	int m=(l+r)>>1;
	
	if(L<=m)update(L,R,c,l,m,rt<<1);
	
	if(R>m)update(L,R,c,m+1,r,(rt<<1)|1);
	
	PushUp(rt,l,r);
	
}

int main()

{
	
	int n,a,b,c,d;
	
	while(cin>>n)
		
	{
		
		int m=0,lmin=10000,rmax=-10000;
		
		for(int i=0;i<n;i++)
			
		{
			
            cin>>a>>b>>c>>d;
			
            lmin=min(lmin,a);
			
			rmax=max(rmax,c);
			
			s[m++]=Seg(a,c,b,1);
			
			s[m++]=Seg(a,c,d,-1);
			
		}
		
		sort(s,s+m);
		
		int ret=0,last=0;
		
		for(int i=0;i<m;i++)
			
		{
			
			if (s[i].l < s[i].r)update(s[i].l,s[i].r-1,s[i].c,lmin,rmax-1,1);
			
			ret+=numSeg[1]*(s[i+1].h-s[i].h);
			
			ret+=abs(len[1]-last);
			
			last=len[1];
			
		}
		
		cout<<ret<<endl;
		
	}
	
}