以下均来自神牛的杰作，可作为参考：
关于线段树的功能基本都在下面阐述，衷心感谢
单点更新:最最基础的线段树,只更新叶子节点,然后把信息用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;
}
}
