本小节主要特点：成段更新，懒惰标记
我对懒惰标记的解释：
如果当前的区间被要更新的区间所覆盖，直接就改变当前结点的信息，
不用再往下了，所以，每次在更新的时候，只更新一层，
把当前结点的信息往下传递一层，以供下一步使用，
如果下一步完成了更新，更新也就结束了，没有完成，
继续往下传递一层。。。。
以下是一些题目，随时更新。。。。
hdu 1698 just a hook
View Code
#include<cstdio>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define mid (l+r)>>1
#define rson m+1,r,rt<<1|1
#define LL rt<<1
#define RR rt<<1|1
const int maxn=111111;
int col[maxn<<2];
int sum[maxn<<2];
void Pushup(int rt){
sum[rt] = sum[LL] + sum[RR];
}
void Pushdown(int rt,int m){
if(col[rt]){//只能在区间被完全覆盖时才把信息往下传，不然没法传，即：如果没有完全覆盖，pushdown相当于没有执行
col[LL] = col[RR] = col[rt];
sum[LL] = (m-(m>>1)) * col[rt];
sum[RR] = (m>>1) * col[rt];
col[rt]=0;
}
}
void build(int l,int r,int rt){
col[rt]=1;
sum[rt]=1;
if(l==r) return ;
int m=mid; build(lson); build(rson);
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] = c * (r - l + 1);
return ;
}
Pushdown(rt,r-l+1);//如果当前结点的区间没有被要覆盖的区间完全盖住，把父亲节点的信息往下传给两个儿子
//懒惰是因为等到了需要更新的时候，才把当前结点的信息更新下去，而不是每次都更新到底
int m=mid;
if(L <= m) update(L , R , c , lson);
if(R > m) update(L , R , c , rson);
Pushup(rt);
}
int main(){
int t,n,m,cases=1;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
build(1 , n , 1);
while(m--){
int a,b,c;
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",cases++,sum[1]);
}
return 0;
}
poj 3468 A Simple Problem with Integers
View Code
#include<cstdio>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define mid (l+r)>>1
#define rson m+1,r,rt<<1|1
#define LL rt<<1
#define RR rt<<1|1
#define lld __int64
const int maxn=111111;
lld col[maxn<<2];
lld sum[maxn<<2];
void Pushup(int rt){
sum[rt] = sum[LL] + sum[RR];
}
void Pushdown(int rt,int m){
if(col[rt]){
col[LL] += col[rt];
col[RR] += col[rt];
sum[LL] += (m-(m>>1)) * col[rt];
sum[RR] += (m>>1) * col[rt];
col[rt]=0;
}
}
void build(int l,int r,int rt){
col[rt]=0;
if(l==r){
scanf("%lld",&sum[rt]);
return ;
}
int m=mid; build(lson); build(rson);
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] += lld(c) * (r - l + 1);
return ;
}
Pushdown(rt , r - l + 1);
int m = mid;
if(L <= m) update(L , R , c , lson);
if(R > m) update(L , R , c , rson);
Pushup(rt);
}
lld 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=mid;
lld ret=0;
if(L <= m) ret += query(L , R , lson);
if(m < R) ret += query(L , R , rson);
return ret;
}
int main(){
int n,q;
scanf("%d%d",&n,&q);
build(1,n,1);
while(q--){
char s[2];
int a,b,c;
scanf("%s",s);
if(s[0]=='Q'){
scanf("%d%d",&a,&b);
printf("%lld\n",query(a,b,1,n,1));
}
else {
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1,n,1);
}
}
return 0;
}
树状数组解法
View Code
树状数组天生用来动态维护数组前缀和，其特点是每次更新一个元素的值，查询只能查数组的前缀和，
但这个题目求的是某一区间的数组和，而且要支持批量更新某一区间内元素的值，怎么办呢？实际上，
还是可以把问题转化为求数组的前缀和。
首先，看更新操作update(s, t, d)把区间A[s]...A[t]都增加d，我们引入一个数组delta[i]，表示
A[i]...A[n]的共同增量，n是数组的大小。那么update操作可以转化为：
1）令delta[s] = delta[s] + d，表示将A[s]...A[n]同时增加d，但这样A[t+1]...A[n]就多加了d，所以
2）再令delta[t+1] = delta[t+1] - d，表示将A[t+1]...A[n]同时减d
然后来看查询操作query(s, t)，求A[s]...A[t]的区间和，转化为求前缀和，设sum[i] = A[1]+...+A[i]，则
A[s]+...+A[t] = sum[t] - sum[s-1]，
那么前缀和sum[x]又如何求呢？它由两部分组成，一是数组的原始和，二是该区间内的累计增量和, 把数组A的原始
值保存在数组org中，并且delta[i]对sum[x]的贡献值为delta[i]*(x+1-i)，那么
sum[x] = org[1]+...+org[x] + delta[1]*x + delta[2]*(x-1) + delta[3]*(x-2)+...+delta[x]*1
= org[1]+...+org[x] + segma(delta[i]*(x+1-i))
= segma(org[i]) + (x+1)*segma(delta[i]) - segma(delta[i]*i)，1 <= i <= x
这其实就是三个数组org[i], delta[i]和delta[i]*i的前缀和，org[i]的前缀和保持不变，事先就可以求出来，delta[i]和
delta[i]*i的前缀和是不断变化的，可以用两个树状数组来维护。
注:用两个树状数组维护
c1[]:用来维护前i项的总改变量，即维护delta[i]的前i项和
c2[]:维护i*delta[i]的前i项和
#include<cstdio>
#include<algorithm>
using namespace std;
#define lld __int64
const int maxn=111111;
lld c1[maxn];
lld c2[maxn];
lld sum[maxn];
int a[maxn];
int n;
int lowbit(int x){
return x&(-x);
}
lld query(lld *arr,int x){
lld ans=0;
while(x>0) {
ans+=arr[x];
x-=lowbit(x);
}
return ans;
}
void update(lld *arr,int x,lld delta){
while(x<=n){
arr[x]+=delta;
x+=lowbit(x);
}
}
int main(){
int q;
scanf("%d%d",&n,&q);
sum[0]=0;
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
while(q--){
char s[2];
int a,b,c;
scanf("%s",s);
if(s[0]=='Q'){
scanf("%d%d",&a,&b);
lld ans=sum[b]-sum[a-1];
ans+=(b+1)*query(c1,b)-query(c2,b);
ans-=a*query(c1,a-1)-query(c2,a-1);
printf("%lld\n",ans);
}
else {
scanf("%d%d%d",&a,&b,&c);
update(c1,a,c);
update(c1,b+1,-c);
update(c2,a,a*c);
update(c2,b+1,-c*(b+1));
}
}
return 0;
}
poj 2528 线段树离散化
注意题目说的是覆盖段，不是覆盖点，离散化的时候可以先把右端点+1
//线段树开大点, 因为点是两倍, 线段树至少得开 maxN * 6
View Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 11111;
bool vis[maxn];
int lx[maxn],rx[maxn];
int lisan[4*maxn];
int col[maxn<<4];
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 , lson);
if(m < R) update(L , R , c , rson);
}
void query(int l,int r,int rt){
if(col[rt] != -1){
if(!vis[col[rt]]) ans++;
vis[col[rt]] = true;
return ;
}
if(l == r) return ;
int m = (l+r)>>1;
query(lson);
query(rson);
}
int find(int key,int n,int x[]){
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 t,n,i,j;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int tot=0;
for(i=0;i<n;i++) {
scanf("%d%d",&lx[i],&rx[i]);
lisan[tot++] = lx[i];
lisan[tot++]=rx[i];
}
sort(lisan,lisan+tot);
int m=1;
for(i=1;i<tot;i++) {
if(lisan[i] != lisan[i-1])
lisan[m++] = lisan[i];
}
for(i=m-1;i>0;i--) {
if(lisan[i] != lisan[i-1]+1)
lisan[m++] = lisan[i]+1;
}
sort(lisan,lisan+m);
memset(col,-1,sizeof(col));
for(i=0;i<n;i++) {
int l=find(lx[i] , m , lisan);
int r=find(rx[i] , m , lisan);
update(l,r,i,0,m,1);
}
ans=0;
memset(vis,0,sizeof(vis));
query(0,m,1);
printf("%d\n",ans);
}
}
poj 3225 区间的各种操作
看了notonlysuccess的代码，看着看着就记住了，关键是看的太久了
U:把区间[l,r]覆盖成1
I:把[-∞,l)(r,∞]覆盖成0
D:把区间[l,r]覆盖成0
C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
S:[l,r]区间0/1互换
成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作
很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了
所以当一个节点得到覆盖标记时把异或标记清空
而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记
开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间)
View Code
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int maxn = 140000;
int col[maxn<<2];
int XOR[maxn<<2];
bool hash[maxn];
void yihuo(int rt){
if(col[rt]!=-1) col[rt]^=1;
else XOR[rt]^=1;
}
void pushdown(int rt){
if(col[rt]!=-1) {
col[rt<<1]=col[rt<<1|1]=col[rt];
XOR[rt<<1]=XOR[rt<<1|1]=0;
col[rt]=-1;
}
if(XOR[rt]){
yihuo(rt<<1);
yihuo(rt<<1|1);
XOR[rt]=0;
}
}
int xor[10];
void update(int l,int r,int rt,int L,int R,char op){
if(L<=l&&r<=R){
if(op=='U'){
col[rt]=1;
XOR[rt]=0;
}
else if(op=='D'){
col[rt]=0;
XOR[rt]=0;
}
else if(op=='C'||op=='S'){
yihuo(rt);
}
return ;
}
pushdown(rt);
int m=(l+r)>>1;
if(L<=m) update(lson,L,R,op);
else if(op=='C'||op=='I'){
XOR[rt<<1]=col[rt<<1]=0;
}
if(R>m) update(rson,L,R,op);
else if(op=='C'||op=='I') {
XOR[rt<<1|1]=col[rt<<1|1]=0;
}
}
void query(int l,int r,int rt){
if(col[rt]==1){
for(int i=l;i<=r;i++){
hash[i]=true;
}
return ;
}
else if(col[rt]==0) return ;
if(l==r) return ;
pushdown(rt);
int m=(l+r)>>1;
query(lson);
query(rson);
}
int main(){
col[1]=XOR[1]=0;
char op,l,r;
int a,b;
while(scanf("%c %c%d,%d%c\n",&op,&l,&a,&b,&r)!=EOF){
a<<=1,b<<=1;
if(l=='(') a++;
if(r==')') b--;
if(a>b){
if(op=='C'||op=='I'){
col[1]=XOR[1]=0;
}
}
else {
update(0,maxn,1,a,b,op);
}
}
memset(hash,false,sizeof(hash));
query(0,maxn,1);
bool flag=false;
int s=-1,e;
for(int i=0;i<=maxn;i++) {
if(hash[i]) {
if(s==-1)
{
s=i;
}
e=i;
}
else {
if(s!=-1)
{
if(flag) printf(" ");
flag=true;
printf("%c%d,%d%c",s&1?'(':'[',s>>1,(e+1)>>1,e&1?')':']');
s=-1;
}
}
}
if(!flag) printf("empty set");
printf("\n");
return 0;
}
zstu 3125
http://acm.zstu.edu.cn:8080/JudgeOnline/showproblem?problem_id=3125
成段增加，区间最值，简单题
View Code
#include<stdio.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid (l+r)>>1
#define LL rt<<1
#define RR rt<<1|1
const int maxn = 111111;
int num[maxn<<2];
int add[maxn<<2];
int pos[maxn<<2];
void pushup(int rt){
if(num[LL]>=num[RR]){
num[rt]=num[LL];
pos[rt]=pos[LL];
}
else {
num[rt]=num[RR];
pos[rt]=pos[RR];
}
}
void pushdown(int rt){
if(add[rt]){
add[LL]+=add[rt];add[RR]+=add[rt];
num[LL]+=add[rt];num[RR]+=add[rt];
add[rt]=0;
}
}
void build(int l,int r,int rt){
add[rt]=num[rt]=0; pos[rt]=l;
if(l==r) return ;
int m=mid; build(lson); build(rson);
}
void update(int L,int R,int delta,int l,int r,int rt){
if(L<=l&&r<=R){
add[rt]+=delta;
num[rt]+=delta;
return ;
}
pushdown(rt);
int m=mid;
if(L<=m) update(L,R,delta,lson);
if(R>m) update(L,R,delta,rson);
pushup(rt);
}
void query(int L,int R,int &id,int &val,int l,int r,int rt){
if(L<=l&&r<=R){
if(val<num[rt]){
val=num[rt];
id=pos[rt];
}
return ;
}
pushdown(rt);
int m=mid;
if(L<=m) query(L,R,id,val,lson);
if(R>m) query(L,R,id,val,rson);
}
int main(){
int n,m,a,b,c;
char s[5];
while(scanf("%d%d",&n,&m),(n||m)){
build(1,n,1);
while(m--){
scanf("%s",s);
if(s[0]=='I'){
scanf("%d%d%d",&a,&b,&c);
update(a,b,c,1,n,1);
}
else {
int index=-1,val=-1;
scanf("%d%d",&a,&b);
query(a,b,index,val,1,n,1);
printf("%d\n",val);
update(index,index,-val,1,n,1);
}
}
}
return 0;
}