ACM大牛的线段树总结。看完就懂了。（代码也是抄自那里。。
hdu1166 （基本线段树（然后表示不明白为什么输出优化WA了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define qwq(x) for(edge *o=head[x];o;o=o->next)
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)) {
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
void print(int x){
char ch[10];int cur=0;
if(x<0) putchar('-'),x=-x;
while(x) ch[++cur]=x%10+'0',x/=10;
for(int i=cur;i;i--) putchar(ch[i]);
putchar('
');
return ;
}
const int nmax=50005;
const int inf=0x7f7f7f7f;
int sum[nmax<<2];
void pushup(int x){
sum[x]=sum[x<<1]+sum[x<<1|1];return ;
}
int query(int l,int r,int x,int tl,int tr){
if(tl<=l&&tr>=r) return sum[x];
int m=(l+r)>>1;int tmp=0;
if(tl<=m) tmp+=query(lson,tl,tr);
if(tr>m) tmp+=query(rson,tl,tr);
return tmp;
}
void build(int l,int r,int x){
if(l==r) {
sum[x]=read();return ;
}
int m=(l+r)>>1;
build(lson);build(rson);pushup(x);
}
void update(int l,int r,int x,int p,int add){
if(l==r) {
sum[x]+=add;return ;
}
int m=(l+r)>>1;
p<=m?update(lson,p,add):update(rson,p,add);
pushup(x);
}
int main(){
int t=read();
rep(i,t){
printf("Case %d:
",i);
int n=read();
build(1,n,1);
char c[10];
while(scanf("%s",c)){
if(c[0]=='E') break;
int a=read(),b=read();
if(c[0]=='Q') printf("%d
",query(1,n,1,a,b));//print(query(1,n,1,a,b));
else if(c[0]=='S') update(1,n,1,a,-b);
else update(1,n,1,a,b);
}
}
return 0;
}
hdu1754 (裸
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=200005;
const int inf=0x7f7f7f7f;
int sum[nmax<<2];
void pushup(int x){
sum[x]=max(sum[x<<1],sum[x<<1|1]);
}
int qmax(int l,int r,int x,int tl,int tr){
if(tl<=l&&tr>=r) return sum[x];
int m=(l+r)>>1;int tmp=-inf;
if(tl<=m) tmp=max(tmp,qmax(lson,tl,tr));
if(tr>m) tmp=max(tmp,qmax(rson,tl,tr));
return tmp;
}
void update(int l,int r,int x,int p,int add){
if(l==r) {
sum[x]=add;return ;
}
int m=(l+r)>>1;
p<=m?update(lson,p,add):update(rson,p,add);
pushup(x);
}
void build(int l,int r,int x){
if(l==r) {
sum[x]=read();return ;
}
int m=(l+r)>>1;
build(lson);build(rson);pushup(x);
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)==2){
build(1,n,1);
rep(i,m){
char c=getchar();int a=read(),b=read();
if(c=='Q') printf("%d
",qmax(1,n,1,a,b));
else update(1,n,1,a,b);
}
}
return 0;
}
hdu1698:区间修改（打标志。。。然后输出的时候.没有输出WA了。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=100005;
int sum[nmax<<2],col[nmax<<2];
void pushup(int x){
sum[x]=sum[x<<1]+sum[x<<1|1];
}
void pushdown(int x,int cnt){
if(col[x]){
col[x<<1]=col[x<<1|1]=col[x];
sum[x<<1]=col[x]*(cnt-(cnt>>1));
sum[x<<1|1]=col[x]*(cnt>>1);
col[x]=0;
}
}
void build(int l,int r,int x){
if(l==r) {
sum[x]=1;return ;
}
int m=(l+r)>>1;
build(lson);build(rson);pushup(x);
}
void update(int tl,int tr,int p,int l,int r,int x){
if(tl<=l&&r<=tr) {
sum[x]=p*(r-l+1);col[x]=p;return ;
}
pushdown(x,r-l+1);
int m=(l+r)>>1;
if(tl<=m) update(tl,tr,p,lson);
if(tr>m) update(tl,tr,p,rson);
pushup(x);
}
int main(){
int t=read();
rep(i,t){
int n=read(),m=read();
clr(col,0);
build(1,n,1);
rep(j,m){
int a=read(),b=read(),c=read();update(a,b,c,1,n,1);
}
printf("Case %d: The total value of the hook is %d.
",i,sum[1]);
}
return 0;
}
poj3468:同样是区间修改。（然后query的时候忘了pushdown了。手动模拟证实不是update写错。。然后一看query。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
#define ll long long
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=100005;
ll sum[nmax<<2],col[nmax<<2];
void pushup(int x){
sum[x]=sum[x<<1]+sum[x<<1|1];
}
void build(int l,int r,int x){
if(l==r){
sum[x]=read();return ;
}
int m=(l+r)>>1;
build(lson);build(rson);pushup(x);
}
void pushdown(int x,int cnt){
if(col[x]){
ll tmp=col[x];
col[x<<1]+=tmp;col[x<<1|1]+=tmp;
sum[x<<1]+=tmp*(cnt-(cnt>>1));
sum[x<<1|1]+=tmp*(cnt>>1);
col[x]=0;
}
return ;
}
void update(int tl,int tr,int p,int l,int r,int x){
if(tl<=l&&tr>=r) {
sum[x]+=(ll)(r-l+1)*p;col[x]+=p;return ;
}
pushdown(x,r-l+1);
int m=(l+r)>>1;
if(tl<=m) update(tl,tr,p,lson);
if(tr>m) update(tl,tr,p,rson);
pushup(x);
}
ll query(int tl,int tr,int l,int r,int x){
if(tl<=l&&r<=tr) return sum[x];
pushdown(x,r-l+1);
int m=(l+r)>>1;ll ans=0;
if(tl<=m) ans+=query(tl,tr,lson);
if(tr>m) ans+=query(tl,tr,rson);
return ans;
}
int main(){
int n=read(),m=read();
build(1,n,1);clr(col,0);
// cout<<sum[1];
// printf("%lld
",query(1,n,1,n,1));
// rep(i,4*n) printf("%d ",sum[i]);
rep(i,m){
char ch=getchar();
if(ch=='Q') {
int a=read(),b=read();
printf("%lld
",query(a,b,1,n,1));
}
else{
int a=read(),b=read(),c=read();
update(a,b,c,1,n,1);
// rep(j,n*4) printf("%d:%d
",j,sum[j]);
}
}
return 0;
}
hdu1394：（其实如果不是数据范围特殊的话根本不能用线段树做。。。逆序对。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=5005;
int sum[nmax<<2],x[nmax];
void pushup(int x){
sum[x]=sum[x<<1]+sum[x<<1|1];
}
void build(int l,int r,int x){
if(l==r) return ;
int m=(l+r)>>1;
build(lson);build(rson);pushup(x);
}
int query(int tl,int tr,int l,int r,int x){
if(tl<=l&&tr>=r) return sum[x];
int m=(l+r)>>1;int ans=0;
if(tl<=m) ans+=query(tl,tr,lson);
if(tr>m) ans+=query(tl,tr,rson);
return ans;
}
void update(int p,int tmp,int l,int r,int x){
if(l==r) {
sum[x]=tmp;return ;
}
int m=(l+r)>>1;
p<=m?update(p,tmp,lson):update(p,tmp,rson);
pushup(x);
return ;
}
int main(){
int n;
while(scanf("%d",&n)==1){
build(1,n,1);clr(sum,0);
int cnt=0;
rep(i,n){
x[i]=read();x[i]++;
if(x[i]!=n) cnt+=query(x[i]+1,n,1,n,1);
update(x[i],1,1,n,1);
}
int ans=cnt;
// cout<<cnt<<endl;
rep(i,n){
cnt=cnt-2*x[i]+n+1;
ans=min(ans,cnt);
}
printf("%d
",ans);
}
return 0;
}
poj2528：线段树+离散化。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=10005;
int col[nmax<<4],v[nmax],x[nmax<<2],lx[nmax],rx[nmax];
int find(int l,int r,int a){
/*int m=(l+r)>>1;
if(x[m]==a) return m;
if(x[m]<a) return find(m+1,r,a);
return find(l,m,a);*/
while(l<=r){
int m=(l+r)>>1;
if(x[m]==a) return m;
if(x[m]<a) l=m+1;
else r=m-1;
}
return -1;
}
void pushdown(int x){
if(col[x]) col[x<<1]=col[x<<1|1]=col[x],col[x]=0; //注意if
}
void update(int tl,int tr,int p,int l,int r,int x){
if(tl<=l&&tr>=r) {
col[x]=p;return ;
}
pushdown(x);
int m=(l+r)>>1;
if(tl<=m) update(tl,tr,p,lson);
if(tr>m) update(tl,tr,p,rson);
}
void query(int l,int r,int x){
if(col[x]) {
v[col[x]]=1;
return ;
}
if(l==r) return ;
int m=(l+r)>>1;
query(lson);query(rson);return ;
}
int main(){
int t=read();
while(t--){
int n=read();x[0]=0;
rep(i,n) x[++x[0]]=lx[i]=read(),x[++x[0]]=rx[i]=read();
sort(x+1,x+n+n+1);
x[0]=0;
rep(i,n+n) if(x[i]!=x[i-1]) x[++x[0]]=x[i];
// rep(i,x[0]) printf("%d ",x[i]); cout<<endl;
int cur=x[0];
rep(i,x[0]-1) if(x[i+1]-x[i]>1) x[++cur]=x[i]+1;
sort(x+1,x+cur+1);
// rep(i,cur) printf("%d ",x[i]);cout<<endl;
clr(col,0);
rep(i,n){
int l=find(1,cur,lx[i]);
int r=find(1,cur,rx[i]);
update(l,r,i,1,cur,1);
// printf("%d %d
",l,r);
}
int ans=0;clr(v,0);query(1,cur,1);
rep(i,n) if(v[i]) ans++;
printf("%d
",ans);
}
return 0;
}
poj3667：求连续最长区间。维护lsum rsum msum即可。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)) {
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=50005;
const int inf=0x7f7f7f7f;
int col[nmax<<2],lsum[nmax<<2],rsum[nmax<<2],msum[nmax<<2];
void pushup(int x,int cnt){
lsum[x]=(lsum[x<<1]==(cnt-(cnt>>1)))?lsum[x<<1]+lsum[x<<1|1]:lsum[x<<1];
rsum[x]=(rsum[x<<1|1]==(cnt>>1))?rsum[x<<1|1]+rsum[x<<1]:rsum[x<<1|1];
msum[x]=max(rsum[x<<1]+lsum[x<<1|1],max(msum[x<<1|1],msum[x<<1]));
}
void pushdown(int x,int cnt){
if(col[x]!=-1){
col[x<<1]=col[x<<1|1]=col[x];
lsum[x<<1]=rsum[x<<1]=msum[x<<1]=col[x]?0:cnt-(cnt>>1);
lsum[x<<1|1]=rsum[x<<1|1]=msum[x<<1|1]=col[x]?0:(cnt>>1);
col[x]=-1;
}
}
void build(int l,int r,int x){
col[x]=-1,msum[x]=lsum[x]=rsum[x]=r-l+1; //col[x]!=0
if(l==r) return ;
int m=(l+r)>>1;build(lson);build(rson);
}
void update(int tl,int tr,int p,int l,int r,int x){
if(tl<=l&&tr>=r){
if(p) col[x]=p,lsum[x]=rsum[x]=msum[x]=0;
else col[x]=p,lsum[x]=rsum[x]=msum[x]=r-l+1;
}else{
pushdown(x,r-l+1);
int m=(l+r)>>1;
if(tl<=m) update(tl,tr,p,lson);
if(tr>m) update(tl,tr,p,rson);
pushup(x,r-l+1);
}
}
int query(int cnt,int l,int r,int x){
if(l==r) return l;
pushdown(x,r-l+1); //look out
int m=(l+r)>>1;
if(msum[x<<1]>=cnt) return query(cnt,lson);
if(rsum[x<<1]+lsum[x<<1|1]>=cnt) return m-rsum[x<<1]+1;
return query(cnt,rson);
}
int main(){
int n=read(),m=read();build(1,n,1);
// rep(i,n<<2) printf("%d:%d %d %d %d
",i,lsum[i],rsum[i],msum[i],col[i]);
rep(i,m){
int p=read();
if(p==1) {
int tmp=read();
if(msum[1]<tmp) puts("0");
else {
int cur=query(tmp,1,n,1);printf("%d
",cur);
update(cur,tmp+cur-1,1,1,n,1);
}
}else{
int a=read(),b=read();update(a,a+b-1,0,1,n,1);
}
}
return 0;
}
hdu2828：题目看起来挺水的。但是update的时候不知道怎么判断QAQ。。。就是不断的插入一些数，如果有了就放在他后面。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep(i,n) for(int i=1;i<=n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define lson l,m,x<<1
#define rson m+1,r,x<<1|1
int read(){
int x=0;char c=getchar();bool f=true;
while(!isdigit(c)){
if(c=='-') f=false;c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return f?x:-x;
}
const int nmax=200005;
const int inf=0x7f7f7f7f;
int sum[nmax<<2],t[nmax<<2],a[nmax],b[nmax];
void build(int l,int r,int x){
if(l==r) {
sum[x]=1;return ;
}
int m=(l+r)>>1;build(lson);build(rson);sum[x]=sum[x<<1]+sum[x<<1|1];
}
/*void update(int p,int add,int l,int r,int x){
if(l==r){
sum[x]=0;t[x]=add;return ;
}
int m=(l+r)>>1;
if(p>m||p<=m&&!sum[x<<1]) update(m+1,add,rson);
else update(p,add,lson);sum[x]=sum[x<<1]+sum[x<<1|1];
}*/
void update(int p,int add,int l,int r,int x){
if(l==r){
sum[x]=0;t[x]=add;return ;
}
int m=(l+r)>>1;
sum[x<<1]>=p?update(p,add,lson):update(p-sum[x<<1],add,rson);
sum[x]=sum[x<<1]+sum[x<<1|1];
}
void query(int l,int r,int x){
if(l==r) {
printf("%d ",t[x]);return ;
}
int m=(l+r)>>1;query(lson);query(rson);return ;
}
int main(){
int n;
while(scanf("%d",&n)==1){
build(1,n,1);
rep(i,n) a[i]=read(),b[i]=read();
for(int i=n;i;i--) update(a[i]+1,b[i],1,n,1)/*,printf("%d
",sum[2])*/;
query(1,n,1);printf("
");
}
return 0;
}