A - 敌兵布阵(模板，基础线段树）

例题：hdu1166

#include <cstdio>
#include <iostream>
using namespace std ;
const int N = 2e5+5 ; 
int a[N] , sum[N] ; 
void bulit(int node , int start, int end){if(start==end){sum[node] = a[start] ; return ; }int mid = (start+end)/2 ; int l = 2*node+1 , r=2*node+2 ; bulit(l,start,mid) ; bulit(r,mid+1,end) ; sum[node] = sum[l]+sum[r] ; 
}
void update(int node,int start,int end,int idx,int val){if(start==end){a[idx] = val ; sum[node] = val ; return ; }int mid = (start+end)/2 ; int l = 2*node+1 , r=2*node+2 ; if(idx>=start&&idx<=mid)    update(l,start,mid,idx,val) ; else    update(r,mid+1,end,idx,val) ;sum[node] = sum[l]+sum[r] ; 
}
int query(int node,int l,int r,int start,int end){if(start>r || end<l)    return 0 ; else if(l<=start&&end<=r)    return sum[node] ; else{int mid=(start+end)/2 ; int left = query(2*node+1,l,r,start,mid) ; int right = query(2*node+2,l,r,mid+1,end) ; return left+right ;}
}  
int main(){int t; scanf("%d",&t) ;for(int j=1 ; j<=t ; ++j){int n; scanf("%d",&n) ; for(int i=0 ; i<n ; ++i)    scanf("%d",&a[i]) ;bulit(0,0,n-1) ; printf ("Case %d:\n",j) ;string s ; while(cin >> s){if(s == "Query"){int l,r ; scanf("%d%d",&l,&r) ; printf("%d\n",query(0,l-1,r-1,0,n-1)) ;}else if(s=="Add"){int idx,val ; scanf("%d%d",&idx,&val) ;update(0,0,n-1,idx-1,a[idx-1]+val) ;  }else if(s=="Sub"){int idx,val; scanf("%d%d",&idx,&val) ;update(0,0,n-1,idx-1,a[idx-1]-val) ; }else if(s == "End")    break ; }}return 0 ; 
}

C - A Simple Problem with Integers（Lazy_tag）

#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring> 
#include <algorithm>
#include <iostream>
using namespace std ; 
typedef long long ll ; 
const int N = 4e5+10 ; 
struct node{int l,r;ll sum,tag ; 
}; 
node tree[N] ;
int a[N] ; 
void push_down(int rt){if(tree[rt].tag){int left=rt<<1 , right=rt<<1|1 ; tree[left].sum += (tree[left].r-tree[left].l+1)*tree[rt].tag ;tree[left].tag += tree[rt].tag ; tree[right].sum += (tree[right].r-tree[right].l+1)*tree[rt].tag ; tree[right].tag += tree[rt].tag ; tree[rt].tag = 0 ;  }
}
void push_up(int rt){tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum ; 
}
void built(int rt,int l,int r){tree[rt].l=l , tree[rt].r=r ;tree[rt].tag=0 ;  if(l==r){tree[rt].sum = a[l] ; return ; }int mid = (l+r)/2 ;  built(rt<<1,l,mid) ; built(rt<<1|1,mid+1,r) ; push_up(rt) ; 
}
void update(int rt,int l,int r,int val){if(l>tree[rt].r || tree[rt].l>r)	return  ; if(l<=tree[rt].l&&tree[rt].r<=r){tree[rt].sum += (tree[rt].r-tree[rt].l+1)*val ; tree[rt].tag += val ; return ; }push_down(rt) ; update(rt<<1,l,r,val) ; update(rt<<1|1,l,r,val) ; push_up(rt) ;  
}
ll query(int rt,int l,int r){if(tree[rt].r<l || tree[rt].l>r)	return 0 ;if(l<=tree[rt].l&&tree[rt].r<=r)	return tree[rt].sum ; push_down(rt) ;ll left = query(rt<<1,l,r) ; ll right = query(rt<<1|1,l,r) ;  return left+right ; 
}
int main(){int n,m ;while(~scanf("%d%d",&n,&m)){for(int i=1 ; i<=n ; ++i)	scanf("%d",&a[i]) ; getchar() ; built(1,1,n) ; char ch[2] ; for(int i=0 ; i<m ; ++i){scanf("%s",ch) ;int x,y,val ;  if(ch[0]=='C'){scanf("%d%d%d",&x,&y,&val) ; update(1,x,y,val) ; }else if(ch[0]=='Q'){scanf("%d%d",&x,&y) ; printf ("%lld\n",query(1,x,y)) ; }}} return 0 ; 
}

D - Mayor’s posters（区间覆盖+离散化）

#include <cstdio>
#include <cmath> 
#include <string.h>
#include <algorithm>
using namespace std ;
const int N = 2e4+10 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
int li[2*N],ri[2*N],ls[N<<2],col[N<<4],sum; 
bool vis[N<<3] ; 
void push_down(int rt){col[rt<<1]=col[rt] ; col[rt<<1|1]=col[rt] ; col[rt]=-1 ; 
} 
// 节点左右区间 节点编号 该段海报编号  海报左右区间 
void update(int l,int r,int rt,int x,int start,int end){
//	printf ("Update %d %d\n",l,r) ; if (start<=l&&r<=end){	//若节点区间在海报区间内则打上海报的编号 col[rt] = x ; return  ; }if (r<start || l>end)	return ;// 若节点区间和海报区间有交叠则打破区间 if (col[rt]!=-1)	push_down(rt) ;// 继续更新 int mid=(l+r)>>1 ; update(l,mid,rt<<1,x,start,end) ; update(mid+1,r,rt<<1|1,x,start,end) ; 
}
void query(int l,int r,int rt){
//	printf ("Query %d %d\n",l,r) ; if (col[rt]!=-1){	//若区间被海报覆盖 if(!vis[col[rt]]){	//该海报未被访问过 ++ sum ; vis[col[rt]]=true ; }return  ; }if (l==r)	return ; 
//	if (col[rt]!=-1)	push_down(rt) ; int mid=(l+r)>>1 ; query(l,mid,rt<<1) ;query(mid+1,r,rt<<1|1) ; 
}
int main(){int t; scanf("%d",&t) ;while(t--){int n ; scanf("%d",&n) ;memset(col,-1,sizeof(col)) ; memset(vis,false,sizeof(vis)) ; sum=0 ; int pos=0 ;  for(int i=1 ; i<=n ; ++i){scanf("%d%d",&li[i],&ri[i]) ; ls[pos++]=li[i] ; ls[pos++]=ri[i] ; }//离散化sort(ls,ls+pos) ; int len = unique(ls,ls+pos)-ls ; int k=len ; for(int i=1 ; i<k ; ++i)if (ls[i]-ls[i-1]>1)ls[len++]=ls[i-1]+1; sort(ls,ls+len) ; for(int i=1 ; i<=n ; ++i){int x = lower_bound(ls,ls+len,li[i])-ls+1 ; int y = lower_bound(ls,ls+len,ri[i])-ls+1 ; 
//			printf ("i=%d x=%d y=%d\n",i,x,y) ; update(1,len,1,i,x,y) ; }query(1,len,1) ; printf ("%d\n",sum) ; }return 0 ;  
}

E - Just a Hook

#include <cstdio>
#include <cmath> 
#include <string.h>
#include <algorithm>
using namespace std ;
const int N = 1e5+10 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
struct node{int l,r ; ll sum,tag ; 
}tree[N<<4] ;  
void push_up(int rt){tree[rt].sum= tree[rt<<1].sum+tree[rt<<1|1].sum ; 
}
void push_down(int rt){if (tree[rt].tag){int l=rt<<1 , r=rt<<1|1 ; tree[l].sum = (tree[l].r-tree[l].l+1)*tree[rt].tag  ;tree[l].tag = tree[rt].tag ; tree[r].sum = (tree[r].r-tree[r].l+1)*tree[rt].tag  ;tree[r].tag = tree[rt].tag ; tree[rt].tag = 0 ; }
}
void built(int rt,int l,int r){tree[rt].l=l , tree[rt].r=r ; tree[rt].tag=0 ; if (l==r){tree[rt].sum=1 ; return ; }int mid=(l+r)>>1 ; built(rt<<1,l,mid) ; built(rt<<1|1,mid+1,r) ; push_up(rt) ; 
}
void update(int l,int r,int rt,int val){if (l<=tree[rt].l&&tree[rt].r<=r){tree[rt].sum = (tree[rt].r-tree[rt].l+1)*val ;tree[rt].tag = val ; return  ; }if (tree[rt].l>r || tree[rt].r<l)	return  ; push_down(rt) ; update(l,r,rt<<1,val) ; update(l,r,rt<<1|1,val) ; push_up(rt) ; 
}
ll query(int l,int r,int rt){if (l<=tree[rt].l&&tree[rt].r<=r)return tree[rt].sum ; if (tree[rt].l>r || tree[rt].r<l)	return 0 ; push_down(rt) ; ll left=query(l,r,rt<<1) ; ll right=query(l,r,rt<<1|1) ;return left+right ; 
}
int main(){int t; scanf("%d",&t) ; for(int cnt=1 ; cnt<=t ; ++cnt){int n; scanf("%d",&n) ; built(1,1,n) ; int m; scanf("%d",&m) ; for(int i=0 ; i<m ; ++i){int l,r,val ; scanf("%d%d%d",&l,&r,&val) ; update(l,r,1,val) ; }printf ("Case %d: The total value of the hook is %lld.\n",cnt,query(1,n,1)) ;}return 0 ;  
}

F - Count the Colors

题意： 给出n条线的左右端点以及线的颜色，打印出能看见颜色的线的颜色编号和能看见的段数。
题解： 和上一道的解法相似，但是这里要用一个last记录旁边的线的颜色，如果不同cnt++

#include <cstdio>
#include <cmath> 
#include <string.h>
#include <algorithm>
using namespace std ;
const int N = 8000 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
int col[N<<4],cnt[N+10],last ; 
void push_down(int rt){if (col[rt]!=-1){col[rt<<1]=col[rt] ; col[rt<<1|1]=col[rt] ; col[rt]=-1 ; }
}
void update(int rt,int c,int l,int r,int start,int end){if (start<=l&&r<=end){col[rt]=c ; return ; }if (l>end || r<start)	return  ; push_down(rt) ; int mid=(l+r)>>1 ; update(rt<<1,c,l,mid,start,end) ; update(rt<<1|1,c,mid+1,r,start,end) ; 
}
void query(int rt,int l,int r){if(col[rt]!=-1&&col[rt]!=last){++cnt[col[rt]];last=col[rt];return  ; }	if (l==r){last = col[rt] ; return;}push_down(rt) ; int mid=(l+r)>>1 ;query(rt<<1,l,mid) ; query(rt<<1|1,mid+1,r) ; 
}
int main(){int n; while(~scanf("%d",&n)){memset(cnt,0,sizeof(cnt)) ; memset(col,-1,sizeof(col)) ; for(int i=0 ; i<n ; ++i){int x,y,c; scanf("%d%d%d",&x,&y,&c) ; update(1,c,1,N,x+1,y) ;}last=-1 ; query(1,1,N) ; for(int i=0 ; i<=8000 ; ++i)if (cnt[i])		printf ("%d %d\n",i,cnt[i]) ; printf ("\n") ; } return 0 ;  
}

G

题意： 给出n个高度，m个询问每次询问x到y之间最高和最低高度相差最大为多少
题解： 直接分两次询问最大值和最小值然后相减即可

#include <cstdio>
#include <cmath> 
#include <string.h>
#include <algorithm>
using namespace std ;
const int N = 5e4+10 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
struct node{int l,r,mx,mn; 
}tree[N<<4] ; 
int a[N] ;
void built(int rt,int l,int r){tree[rt].l=l , tree[rt].r=r ; if(l==r){tree[rt].mx=a[l], tree[rt].mn=a[l] ; return ; }int mid=(l+r)>>1 ; built(rt<<1,l,mid) ;built(rt<<1|1,mid+1,r) ; tree[rt].mx = max(tree[rt<<1].mx,tree[rt<<1|1].mx) ; tree[rt].mn = min(tree[rt<<1].mn,tree[rt<<1|1].mn) ; 
}
int queryMx(int rt,int l,int r){if (l<=tree[rt].l&&tree[rt].r<=r)	return tree[rt].mx ; if (tree[rt].l>r || tree[rt].r<l)	return 0 ; int left = queryMx(rt<<1,l,r) ; int right = queryMx(rt<<1|1,l,r) ; return max(left,right) ;  
}
int queryMn(int rt,int l,int r){if (l<=tree[rt].l&&tree[rt].r<=r)	return tree[rt].mn ; if (tree[rt].l>r || tree[rt].r<l)	return INF ; int left = queryMn(rt<<1,l,r) ; int right = queryMn(rt<<1|1,l,r) ; return min(left,right) ; 
}
int main(){int n,m; while(~scanf("%d%d",&n,&m)){for(int i=1 ; i<=n ; ++i)	scanf("%d",&a[i]) ; built(1,1,n) ; for(int i=1 ; i<=m ; ++i){int x,y; scanf("%d%d",&x,&y) ; int mx=queryMx(1,x,y) , mn=queryMn(1,x,y) ; printf ("%d\n",mx-mn) ; }} return 0 ;  
}

H - Can you answer these queries?

题意： 给出n只旗舰的防御值，m个操作，1 x y 询问[x,y]的防御值总和，0 x y 使得区间[x,y] 内的防御值变为原来的sqrt(四舍五入)。
**题解： ** 因为数据不大，所以直接到叶子节点处sqrt，如果叶子节点都为1，即sum==区间长度就不用更新，其他操作是基础的线段树。

#include <cstdio>
#include <cmath> 
#include <string.h>
#include <algorithm>
using namespace std ;
const int N = 1e5+10 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
struct node{int l,r;ll sum; 
}tree[N<<4] ;
ll a[N] ;  
void built(int rt,int l,int r){tree[rt].l=l , tree[rt].r=r ; if(l==r){tree[rt].sum=a[l] ; return ; }int mid=(l+r)>>1 ; built(rt<<1,l,mid) ;built(rt<<1|1,mid+1,r) ; tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum ; 
}
void update(int rt,int l,int r){if (tree[rt].l>r || tree[rt].r<l)	return  ; if (tree[rt].sum==(tree[rt].r-tree[rt].l+1))	return ;if (tree[rt].l==tree[rt].r){tree[rt].sum=(ll)sqrt(tree[rt].sum*1.0); ;return ; }update(rt<<1,l,r) ;update(rt<<1|1,l,r) ; tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum ;  
}
ll query(int rt,int l,int r){if (l<=tree[rt].l&&tree[rt].r<=r)	return tree[rt].sum ; if (tree[rt].l>r || tree[rt].r<l)	return (ll)0 ; ll left=query(rt<<1,l,r) ; ll right=query(rt<<1|1,l,r) ;return left+right ;  
}
int main(){int n,cnt=0; while(~scanf("%d",&n)){printf ("Case #%d:\n",++cnt) ; for(int i=1 ; i<=n ; ++i)	scanf("%lld",&a[i]) ; built(1,1,n) ; int m; scanf("%d",&m) ; for(int i=1 ; i<=m ; ++i){int t,x,y; scanf("%d%d%d",&t,&x,&y) ; if (x>y)	swap(x,y) ; if(t==1)	printf("%lld\n",query(1,x,y)) ; else	update(1,x,y) ; }printf ("\n") ; } return 0 ;  
}

I - Tunnel Warfare （线段树维护连续区间）

#include <cstdio>
#include <cmath> 
#include <string>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std ;
const int N = 5e4+10 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
struct node{int l,r,pre,suf,mxlen ; 
}tree[N<<4] ;
int st[N] ; 
void push_up(int rt){tree[rt].pre = tree[rt<<1].pre ; tree[rt].suf = tree[rt<<1|1].suf ; tree[rt].mxlen = max(tree[rt<<1].mxlen,tree[rt<<1|1].mxlen) ; tree[rt].mxlen = max(tree[rt].mxlen , tree[rt<<1].suf+tree[rt<<1|1].pre) ; if (tree[rt<<1].pre==tree[rt<<1].r-tree[rt<<1].l+1)tree[rt].pre += tree[rt<<1|1].pre ; if (tree[rt<<1|1].suf == tree[rt<<1|1].r-tree[rt<<1|1].l+1)tree[rt].suf += tree[rt<<1].suf ; 
}
void built(int rt,int l,int r){tree[rt].l=l , tree[rt].r=r ;tree[rt].pre=tree[rt].suf=tree[rt].mxlen=r-l+1 ;if (l==r)	return ;int mid=(l+r)>>1 ; built(rt<<1,l,mid) ; built(rt<<1|1,mid+1,r) ;  
}
void update(int rt,int idx,int val){if (tree[rt].l==tree[rt].r){if(val)		tree[rt].pre=tree[rt].suf=tree[rt].mxlen=1 ; else	tree[rt].pre=tree[rt].suf=tree[rt].mxlen=0 ; return  ; }int mid = (tree[rt].l+tree[rt].r)>>1 ; if (idx<=mid)		update(rt<<1,idx,val) ; else	update(rt<<1|1,idx,val) ; push_up(rt) ; 
}
int query(int rt,int t){if (tree[rt].l==tree[rt].r || tree[rt].mxlen==0 || tree[rt].mxlen==tree[rt].r-tree[rt].l+1)return tree[rt].mxlen ; int mid = (tree[rt].l+tree[rt].r)>>1 ; if (t<=mid)	{if (t>=tree[rt<<1].r-tree[rt<<1].suf+1)return query(rt<<1,t)+query(rt<<1|1,mid+1) ; else	return query(rt<<1,t) ; }else{if(t<=tree[rt<<1|1].l+tree[rt<<1|1].pre-1)return query(rt<<1|1,t)+query(rt<<1,mid) ;else	return query(rt<<1|1,t) ; 	}
}
int main(){int n,m;while(~scanf("%d%d",&n,&m)){char con[2] ; int x ;built(1,1,n) ; int pos=0 ; for(int i=0 ; i<m ; ++i){scanf("%s",con) ; if (con[0]=='R'){x=st[--pos] ; update(1,x,1) ;  }else if(con[0]=='D'){scanf("%d",&x) ;st[pos++]=x ;update(1,x,0) ; }else if(con[0]=='Q'){scanf("%d",&x) ;printf ("%d\n",query(1,x)) ;  }}}return 0 ;  
}

J - Assign the task （dfs+线段树）

题意： 每一个员工都有一个直接上司（一棵有向树），当给一个人分配工作时，他的下属也会被分配到该工作，给出n个人的关系，还有m个操作，C x为询问x当前的工作，T x y为给x分配y工作。
题解： 先按dfs建树，
然后按常规建立线段树，修改的时候就是修改dfs树中的段，例如给3分配任务1，那就是把344113这段的任务改成1。

#include <cstdio>
#include <cmath> 
#include <string>
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std ;
const int N = 5e4+10 ;
const int mod = 1e9+7 ;
const int INF=1e6 ; 
typedef long long ll ;
vector<int> g[N] ; 
bool vis[N] ; 
int cnt,L[N],R[N];
struct node{int l,r,task ; 
}tree[N<<4] ; 
void dfs(int x){L[x]=cnt++ ;for(int i=0 ; i<g[x].size() ; ++i)	dfs(g[x][i]) ;R[x]=cnt++; 
}
void built(int rt,int l,int r){tree[rt].l=l , tree[rt].r=r , tree[rt].task=-1 ; if(l==r)	return ;int mid=(l+r)>>1 ;built(rt<<1,l,mid) ;built(rt<<1|1,mid+1,r) ; 
}
void push_up(int rt){if(tree[rt<<1].task==tree[rt<<1|1].task)tree[rt].task = tree[rt<<1].task ; else	tree[rt].task=-1 ;
}
void push_down(int rt){if(tree[rt].task!=-1){tree[rt<<1].task=tree[rt].task ; tree[rt<<1|1].task=tree[rt].task ; tree[rt].task=-1 ;}
}
void update(int rt,int l,int r,int t){if(tree[rt].r<l || tree[rt].l>r)	return  ;if(l<=tree[rt].l&&tree[rt].r<=r){tree[rt].task=t ; return ; }	push_down(rt) ; update(rt<<1,l,r,t) ; update(rt<<1|1,l,r,t) ; push_up(rt) ; 
}
int query(int rt,int t){if (tree[rt].l==tree[rt].r)		return tree[rt].task ;push_down(rt) ; int mid=(tree[rt].l+tree[rt].r)>>1 ; if(t<=mid)		return query(rt<<1,t) ; else	return query(rt<<1|1,t) ; 
}
int main(){int t; scanf("%d",&t);for(int tt=1 ; tt<=t ; ++tt){int n; scanf("%d",&n) ;for(int i=1 ; i<=n ; ++i)	g[i].clear();memset(vis,false,sizeof(vis)) ; memset(L,-1,sizeof(L)) ; memset(R,-1,sizeof(R)) ;  for(int i=1 ; i<n ; ++i){int u,v; scanf("%d%d",&u,&v) ; g[v].push_back(u) ;vis[u]=true ; }cnt=1 ; for(int i=1 ; i<=n ; ++i){if(!vis[i]){dfs(i); break;}}built(1,1,2*n) ; int m; scanf("%d",&m) ; printf ("Case #%d:\n",tt) ; for(int i=0 ; i<m ; ++i){char con[2] ; scanf("%s",con) ;if(con[0]=='T'){int x,y; scanf("%d%d",&x,&y) ; update(1,L[x],R[x],y) ; 		}else if(con[0]=='C'){int x; scanf("%d",&x) ; printf ("%d\n",query(1,L[x])) ;}}} return 0 ;  
}