【题意】：
n个阵营一字排开，每个初始有a[i]个人。现有两种操作：
Q a b 查询[a,b]之间总人数并输出
A/S a b 在a号位添加/删除b个人
【分析】：最基本的单点更新和区间查询，维护节点信息sum[o]
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 5 using namespace std; 6 7 int numv[50005<<2]; 8 int A[50005]; 9 10 void builtTree(int o,int l,int r){ 11 if(l==r) { 12 numv[o]=A[l]; 13 return ; 14 } 15 int m=l+(r-l)/2; 16 builtTree(2*o,l,m); 17 builtTree(2*o+1,m+1,r); 18 numv[o]=numv[2*o]+numv[2*o+1]; 19 return ; 20 } 21 void Update(int o,int l,int r,int p,int x){ 22 if(l==r && l==p){ 23 A[l]=x; 24 numv[o]=x; 25 return ; 26 } 27 int m=l+(r-l)/2; 28 if (p<=m) Update(2*o,l,m,p,x); 29 if (p>=m+1)Update(2*o+1,m+1,r,p,x); 30 numv[o]=numv[2*o]+numv[2*o+1]; 31 } 32 int Query(int ql,int qr,int o,int l,int r){ 33 if (ql<=l && r<=qr) return numv[o]; 34 int m=l+(r-l)/2; 35 int ans=0; 36 if (ql<=m) ans+=Query(ql,qr,2*o,l,m); 37 if (m+1<=qr) ans+=Query(ql,qr,2*o+1,m+1,r); 38 return ans; 39 } 40 int t,n; 41 int main(){ 42 scanf("%d",&t); 43 for(int cas=1;cas<=t;cas++){ 44 scanf("%d",&n); 45 printf("Case %d: ",cas); 46 for(int i=1;i<=n;i++) scanf("%d",&A[i]); 47 builtTree(1,1,n); 48 char s[105]; 49 while(~scanf("%s",s)){ 50 if (s[0]=='E') { 51 break; 52 } 53 int a,b; 54 scanf("%d%d",&a,&b); 55 if (s[0]=='Q'){ 56 int ans=Query(a,b,1,1,n); 57 printf("%d ",ans); 58 } 59 if (s[0]=='A'){ 60 Update(1,1,n,a,A[a]+b); 61 } 62 if (s[0]=='S'){ 63 Update(1,1,n,a,A[a]-b); 64 } 65 } 66 } 67 return 0; 68 }
【题意】:给n个数字。m次操作，每次操作更新一个数字或者查询区间最大值。
【分析】：基本单点更新区间查询，维护节点信息max[o]
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #define Mod 1000000007 5 #define LL long long 6 #define toL 2*o,l,m 7 #define toR 2*o+1,m+1,r 8 using namespace std; 9 10 int maxv[200005<<2]; 11 int A[200005]; 12 13 void builtTree(int o,int l,int r){ 14 if (l==r){ 15 maxv[o]=A[l]; 16 return ; 17 } 18 int m=(l+r)/2; 19 builtTree(toL); 20 builtTree(toR); 21 maxv[o]=max(maxv[2*o],maxv[2*o+1]); 22 return ; 23 } 24 void Updata(int o,int l,int r,int p,int x){ 25 if (l==r && p==l){ 26 maxv[o]=x; 27 return ; 28 }else { 29 int m=(r+l)/2; 30 if (p<=m) Updata(toL,p,x); 31 if (m+1<=p) Updata(toR,p,x); 32 maxv[o]=max(maxv[2*o],maxv[2*o+1]); 33 return ; 34 } 35 } 36 int Query(int o,int l,int r,int ql,int qr){ 37 if (ql<=l && r<=qr) return maxv[o]; 38 int m=(r+l)/2; 39 int ans=-1; 40 if (ql<=m) ans=max(ans,Query(toL,ql,qr)); 41 if (m+1<=qr) ans=max(ans,Query(toR,ql,qr)); 42 return ans; 43 } 44 int n,q; 45 46 int main(){ 47 while(~scanf("%d%d",&n,&q)){ 48 for(int i=1;i<=n;i++) scanf("%d",&A[i]); 49 builtTree(1,1,n); 50 for(int i=1;i<=q;i++){ 51 int a,b; 52 char s[3]; 53 scanf("%s%d%d",s,&a,&b); 54 if (s[0]=='Q'){ 55 printf("%d ",Query(1,1,n,a,b)); 56 } 57 if (s[0]=='U'){ 58 Updata(1,1,n,a,b); 59 } 60 } 61 } 62 return 0; 63 }
【题意】:就是给出一串数，当依次在将第一个数变为最后一个数的过程中，要你求它的最小逆序数。
【分析】:每次维护sumv求区间内有多少个数字，处理出LOW[],UP[]后利用sum每次枚举
for(int i=1;i<=n;i++){
scanf("%d",&A[i]);
A[i]++;
// cout<<"Q="<<Query(1,1,n,A[i]+1,n)<<endl;
if (A[i]+1<=n) sum+=Query(1,1,n,A[i]+1,n);
updata(1,1,n,A[i],1);//令A【i】的位置为1，那么sunv就相当于一个求和了
A[i]--;//信息已经保存到树中，A[i]可还原
}
【代码】：
1 /*HDU1394搜索写法*/ 2 #include <iostream> 3 #include <string.h> 4 #include <stdio.h> 5 #define LL 2*o,l,m 6 #define LR 2*o+1,m+1,r 7 using namespace std; 8 9 int A[50005]; 10 int Low[50005],Up[50005]; 11 int numv[50005<<2];//[1...50005]有多少个数 12 13 int Query(int o,int l,int r,int ql,int qr){ 14 if (ql<=l && r<=qr) return numv[o]; 15 int m=(r+l)>>1; 16 int ans=0; 17 if (ql<=m) ans+=Query(LL,ql,qr); 18 if (m+1<=qr) ans+=Query(LR,ql,qr); 19 return ans; 20 } 21 void updata(int o,int l,int r,int p,int x){ 22 // cout<<"l="<<l<<","<<"r="<<r<<endl; 23 24 if (l==r && p==l) { 25 numv[o]=1; 26 return ; 27 } 28 int m=(r+l)>>1; 29 if (p<=m)updata(LL,p,x); 30 if (m+1<=p)updata(LR,p,x); 31 numv[o]=numv[2*o]+numv[2*o+1]; 32 return; 33 } 34 int main(){ 35 int n; 36 while(~scanf("%d",&n)){ 37 memset(numv,0,sizeof(numv)); 38 int ans,sum=0; 39 for(int i=1;i<=n;i++){ 40 scanf("%d",&A[i]); 41 A[i]++; 42 // cout<<"Q="<<Query(1,1,n,A[i]+1,n)<<endl; 43 if (A[i]+1<=n) sum+=Query(1,1,n,A[i]+1,n); 44 updata(1,1,n,A[i],1);//令A【i】的位置为1，那么sunv就相当于一个求和了 45 A[i]--;//信息已经保存到树中，A[i]可还原 46 } 47 ans=sum; 48 for(int i=0;i<n;i++){ 49 Low[i]=i; 50 Up[i]=n-i-1; 51 } 52 for(int i=1;i<=n-1;i++){ 53 sum=sum+(Up[A[i]]-Low[A[i]]); 54 ans=min(sum,ans); 55 } 56 printf("%d ",ans); 57 } 58 return 0; 59 }
【题意】:有一块长方形的广告板，往上面贴广告，然后给n个1*wi的广告，要求把广告贴上去，如果前面的行可以贴，就要贴前面的并且要靠左贴，前面的贴不下就贴在下面，广告的高度是wi，如果能贴在上面输出最小的高度，如果不能就输出-1。
【分析】：以h为轴建立线段树，每次维护区间内剩余A[i]的最大值max[o]，假设我们要新增的广告的长度为L
那么，当max[o]<L的时候肯定已经不能放置，因为每次挨着左边的放，所以每次剩余的A[i]=A[i]-L即可
【代码】：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<stdlib.h> 6 #define Lson l,m,2*o 7 #define Rson m+1,r,2*o+1 8 using namespace std; 9 int maxv[200100<<2]; 10 void updata(int l,int r,int o,int p,int x){ 11 if (l==r){ 12 maxv[o]=x; 13 return ; 14 }else { 15 int m=(l+r)>>1; 16 if (p<=m)updata(Lson,p,x); 17 else updata(Rson,p,x); 18 maxv[o]=max(maxv[2*o],maxv[2*o+1]); 19 } 20 return ; 21 } 22 int h,w,n; 23 void builtTree(int l,int r,int o){ 24 if (l==r) { 25 maxv[o]=w; 26 return ; 27 } 28 int m=(r+l)>>1; 29 builtTree(Lson); 30 builtTree(Rson); 31 maxv[o]=max(maxv[2*o],maxv[2*o+1]); 32 return ; 33 } 34 int Query(int l,int r,int o,int x){ 35 if (l==r){ 36 updata(1,h,1,l,maxv[o]-x); 37 return l; 38 }else { 39 int m=(r+l)>>1; 40 if (maxv[2*o]>=x) return Query(Lson,x); 41 else return Query(Rson,x); 42 } 43 } 44 int main(){ 45 while(~scanf("%d%d%d",&h,&w,&n)){ 46 if (h>n) h=n; 47 builtTree(1,h,1); 48 while(n--){ 49 int x; 50 scanf("%d",&x); 51 if (maxv[1]<x)//没有任何地方可以放 52 { 53 puts("-1"); 54 }else { 55 printf("%d ",Query(1,h,1,x)); 56 } 57 } 58 } 59 return 0; 60 }
【题意】:给你N个数，Q个操作，操作有两种，‘Q a b ’是询问a~b这段数的和，‘C a b c’是把a~b这段数都加上c。
【分析】：成段更新，每次给区间的每个元素加上C，那么当用到下层节点的时候，再把标记下传，更新区间即可，标记是这个区间的每个数要增加的C值，
当一段被重复覆盖时，更新C即可，当标记下传后，这段区间的sum已经增加过了len*C,那么区间对应的标记减去C即可。区间标记的C为0时，表示更新完毕了。
【代码】：
1 /*poj3468 2 */ 3 #include<iostream> 4 #include<stdio.h> 5 #include<string.h> 6 #include<algorithm> 7 #include<stdlib.h> 8 #define Lson l,m,2*o 9 #define Rson m+1,r,2*o+1 10 #define LL long long 11 using namespace std; 12 13 LL sum[100010<<2]; 14 LL add[100010<<2]; 15 LL A[100010]; 16 void PushDown(int o,int len){ 17 if (add[o]){ 18 add[2*o]+=add[o]; 19 add[2*o+1]+=add[o]; 20 sum[2*o]+=add[o]*(len-(len>>1)); 21 sum[2*o+1]+=add[o]*(len>>1); 22 add[o]=0; 23 } 24 return ; 25 } 26 void PushUp(int o){ 27 sum[o]=sum[2*o]+sum[2*o+1]; 28 } 29 void builtTree(int l,int r,int o){ 30 add[o]=0; 31 if (l==r){ 32 sum[o]=A[l]; 33 }else { 34 int m=(l+r)>>1; 35 builtTree(Lson); 36 builtTree(Rson); 37 PushUp(o); 38 } 39 return ; 40 } 41 LL Query(int l,int r,int o,int L,int R){ 42 if (L<=l && r<=R){ 43 return sum[o]; 44 } 45 PushDown(o,r-l+1); 46 int m=(l+r)>>1; 47 LL ans=0; 48 if (L<=m) ans+=Query(Lson,L,R); 49 if (m+1<=R) ans+=Query(Rson,L,R); 50 return ans; 51 } 52 void Updata(int l,int r,int o,int L,int R,int x){ 53 if (L<=l && r<=R){ 54 sum[o]+=(LL)(r-l+1)*(LL)x; 55 add[o]+=x; 56 return ; 57 } 58 PushDown(o,r-l+1); 59 int m=(r+l)>>1; 60 if (L<=m) Updata(Lson,L,R,x); 61 if (m+1<=R) Updata(Rson,L,R,x); 62 PushUp(o); 63 return ; 64 } 65 int N,Q; 66 int main(){ 67 //// freopen("out.txt","w",stdout); 68 while(~scanf("%d%d",&N,&Q)){ 69 for(int i=1;i<=N;i++) scanf("%lld",&A[i]); 70 builtTree(1,N,1); 71 char s[10]; 72 while(Q--){ 73 scanf("%s",s); 74 int l,r,x; 75 if (s[0]=='Q'){ 76 scanf("%d%d",&l,&r); 77 printf("%lld ",Query(1,N,1,l,r)); 78 } 79 if (s[0]=='C'){ 80 scanf("%d%d%d",&l,&r,&x); 81 Updata(1,N,1,l,r,x); 82 } 83 } 84 } 85 return 0; 86 }
【题意】：那个城市里要竞选市长，然后在一块墙上可以贴海报为自己拉票，每个人可以贴连续的一块区域，后来帖的可以覆盖前面的，问到最后一共可以看到多少张海报。1 <= n <= 10000 ，1 <= i <= n, 1 <= li <= ri <= 10000000 .
【分析】：首先看这个N的范围，基本上是和区间有关的操作。
如果把新增一张海报 I 当做把一个区间的数字都变成 I+1，我们想要的是一段区间里不同的数字的个数num[o]。
显然，我们不可能把一个区间的数字都更新完了再花O（R-L）的时间更新这个值num[o]。
那么怎么办呢？我们向区间的合并上考虑。
【代码】：具体的分析看代码注释：
/*解题的重点：
1、区间更新成一个数，用lazy标记
2、左边的范围很大，用离散化
3、离散化处理，二分查找出x的对应序号
4、查询，对于col[o]>0的区间说明，这个区间都是col[o]，直接ans+1返回即可
但是因为计算的是露出的海报的总的种数，所以查找过的点不需要再计算。
也能保证单点的col[o]大于0，因为col标记不需要下传
5、但是题目略有歧义，这个更新的(l,r)是不是坐标轴上的点呢？
是的话，要处理成(l,r-1)。
*/
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<map> 7 #define Lson l,m,2*o 8 #define Rson m+1,r,2*o+1 9 #define LL long long 10 using namespace std; 11 12 int lx[41111]; 13 int rx[41111]; 14 int px[41111<<1]; 15 int col[41111<<3]; 16 bool vis[41111<<1]; 17 18 /*解题的重点： 19 1、区间更新成一个数，用lazy标记 20 2、左边的范围很大，用离散化 21 3、离散化处理，二分查找出x的对应序号 22 4、查询，对于col[o]>0的区间说明，这个区间都是col[o]，直接ans+1返回即可 23 但是因为计算的是露出的海报的总的种数，所以查找过的点不需要再计算。 24 也能保证单点的col[o]大于0，因为col标记不需要下传 25 5、但是题目略有歧义，这个更新的(l,r)是不是坐标轴上的点呢？ 26 是的话，要处理成(l,r-1)。 27 */ 28 int T,N,cnt,ans; 29 int binary(int n,int x){//px[0]--px[n-1]中找到x 30 int ans; 31 ans=lower_bound(px,px+n,x)-px; 32 return ans+1; 33 } 34 void PushDown(int o){ 35 if (col[o]){ 36 col[2*o]=col[o]; 37 col[2*o+1]=col[o]; 38 col[o]=0; 39 } 40 return; 41 } 42 43 void Query(int l,int r,int o){// 44 if (col[o]){//以区间代替点 45 if (!vis[col[o]]){//不必查找到每一个点，区间代替下面的每个单点即可 46 ans++; 47 vis[col[o]]=true; 48 } 49 return ; 50 } 51 if (l==r) return ;//单点保证在上面处理过了 52 int m=(l+r)>>1; 53 Query(Lson); 54 Query(Rson); 55 } 56 void Updata(int l,int r,int o,int L,int R,int x){ 57 if (L<=l&&r<=R){//给找到的区间加懒惰标记 58 col[o]=x; 59 return ; 60 } 61 PushDown(o);//若是要向下层更新，那么懒惰标记要下传 62 int m=(l+r)>>1; 63 if (L<=m) Updata(Lson,L,R,x); //继续向下搜索更新 64 if (m+1<=R) Updata(Rson,L,R,x); 65 return ; 66 } 67 int main(){ 68 scanf("%d",&T); 69 while(T--){ 70 scanf("%d",&N); 71 cnt=0; 72 for(int i=0;i<N;i++){//离散化 73 scanf("%d",&lx[i]); 74 scanf("%d",&rx[i]); 75 px[cnt++]=lx[i]; 76 px[cnt++]=rx[i]; 77 } 78 sort(px,px+cnt); 79 int cnt2=0; 80 px[cnt]=-1; 81 for(int i=0;i<cnt;i++){ 82 if (px[i]!=px[i+1]) px[cnt2++]=px[i];//去重并且按顺序统计离散的点 83 } 84 ans=0; 85 memset(vis,0,sizeof(vis)); 86 memset(col,0,sizeof(col)); 87 for(int i=0;i<N;i++){ 88 int k1=binary(cnt2,lx[i]),k2=binary(cnt2,rx[i]);//二分查找到标号 89 Updata(1,cnt2,1,k1,k2,i+1); 90 } 91 Query(1,cnt2,1); 92 printf("%d ",ans); 93 94 } 95 return 0; 96 }
POJ 3667 （重难点）
【题意】：
有N个房间，M次操作。1 a表示找到连续的长度为a的空房间，如果有多解，优先左边的，即表示入住，输出入住的人的最左边的房间号。2 b len把起点为b长度的len的房间清空，即退房。
【分析】：
假设：如果房间没人，标记为1，否则标记为0
首先，我们肯定是想快速查找出一段区间内是否有满足的连续长度的0的存在，但是线段树的区间已经固定好了。
但是有可能存在两个区间合起来中间有长度为L的连续空房间。
那么我们就要维护：
Lsum[o]：区间左边连续的0的个数
Rsum[o]：区间右边连续的0的个数
Msum[o]: 区间中最大的连续的0的个数
那么当我们查找区间o（保证Msum[o]>=Num）时，因为要尽量的向左分配，所以若Msum[2*o]当然向左分配，若Rsum[2*o]+Lsum[2*o+1]>=Num，则直接可以计算出入住的位置p= m-Rsum[2*o]+1;
int Query(int l,int r,int o,int D){//向左搜索
int m=(r+l)>>1;
if (l==r){//当且D==1时才会有这个出口
return l;
}
PushDown(o,r-l+1);
if (max_sub[2*o]>=D){
return Query(Lson,D);
}else {
if (max_suffix[2*o]+max_prefix[2*o+1]>=D){
return m-max_suffix[2*o]+1;
}
}
return Query(Rson,D);
}
区间更新：
1、有两种：分别是一段区间更新为1,或 0
2、Pushdown标记PushUp标记
3、关键是同时维护：sum[o]
if (L<=l && r<=R){
col[o]=x;
max_sub[o]=max_suffix[o]=max_prefix[o]=(r-l+1)*x;
return;
}
4、区间合并，维护信息
void PushUp(int l,int r,int o){
int m=(r+l)>>1;
int l1=m-l+1,l2=r-(m+1)+1;
max_sub[o]=max(max_sub[2*o],max_sub[2*o+1]);
max_sub[o]=max(max_sub[o],max_suffix[2*o]+max_prefix[2*o+1]);
if (max_prefix[2*o]==l1){
max_prefix[o]=l1+max_prefix[2*o+1];//整个区间可以合并
}else max_prefix[o]=max_prefix[2*o];
if (max_suffix[2*o+1]==l2){
max_suffix[o]=l2+max_suffix[2*o];
}else max_suffix[o]=max_suffix[2*o+1];
return ;
}
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #define maxn 51000 5 #define Lson l,m,2*o 6 #define Rson m+1,r,2*o+1 7 using namespace std; 8 int col[maxn<<2]; 9 int max_sub[maxn<<2];//连续的1的个数 10 int max_prefix[maxn<<2];//靠左的连续的1的个数 11 int max_suffix[maxn<<2];//靠右的连续的1的个数 12 int N,M; 13 void PushUp(int l,int r,int o){ 14 int m=(r+l)>>1; 15 int l1=m-l+1,l2=r-(m+1)+1; 16 max_sub[o]=max(max_sub[2*o],max_sub[2*o+1]); 17 max_sub[o]=max(max_sub[o],max_suffix[2*o]+max_prefix[2*o+1]); 18 if (max_prefix[2*o]==l1){ 19 max_prefix[o]=l1+max_prefix[2*o+1];//整个区间可以合并 20 }else max_prefix[o]=max_prefix[2*o]; 21 if (max_suffix[2*o+1]==l2){ 22 max_suffix[o]=l2+max_suffix[2*o]; 23 }else max_suffix[o]=max_suffix[2*o+1]; 24 return ; 25 } 26 //1表示房间空，0表示不可用 27 void PushDown(int o,int len)//因为有区间上的清零，所以要PushDown 28 { 29 if (col[o]==-1) return; 30 col[2*o]=col[o]; 31 col[2*o+1]=col[o]; 32 if (col[o]==1){ 33 max_sub[2*o]=max_suffix[2*o]=max_prefix[2*o]=(len-(len>>1)); 34 max_sub[2*o+1]=max_suffix[2*o+1]=max_prefix[2*o+1]=len>>1; 35 } 36 if (col[o]==0){ 37 max_sub[2*o]=max_suffix[2*o]=max_prefix[2*o]=0; 38 max_sub[2*o+1]=max_suffix[2*o+1]=max_prefix[2*o+1]=0; 39 } 40 col[o]=-1; 41 } 42 void Updata(int l,int r,int o,int L,int R,int x){ 43 if (L<=l && r<=R){ 44 col[o]=x; 45 max_sub[o]=max_suffix[o]=max_prefix[o]=(r-l+1)*x; 46 return; 47 } 48 PushDown(o,r-l+1); 49 int m=(l+r)>>1; 50 if (L<=m) Updata(Lson,L,R,x); 51 if (m+1<=R) Updata(Rson,L,R,x); 52 PushUp(l,r,o); 53 return; 54 } 55 int Query(int l,int r,int o,int D){//向左搜索 56 int m=(r+l)>>1; 57 if (l==r){//当且D==1时才会有这个出口 58 return l; 59 } 60 PushDown(o,r-l+1); 61 if (max_sub[2*o]>=D){ 62 return Query(Lson,D); 63 }else { 64 if (max_suffix[2*o]+max_prefix[2*o+1]>=D){ 65 return m-max_suffix[2*o]+1; 66 } 67 } 68 return Query(Rson,D); 69 } 70 71 void BuiltTree(int l,int r,int o){ 72 col[o]=-1; 73 if (l==r){ 74 max_sub[o]=1; 75 max_suffix[o]=1; 76 max_prefix[o]=1; 77 return ; 78 } 79 int m=(l+r)>>1; 80 BuiltTree(Lson); 81 BuiltTree(Rson); 82 PushUp(l,r,o); 83 return ; 84 } 85 int main(){ 86 while(~scanf("%d%d",&N,&M)){ 87 BuiltTree(1,N,1); 88 int q,a,b; 89 while(M--){ 90 scanf("%d",&q); 91 if (q==1){ 92 scanf("%d",&a); 93 if (max_sub[1]<a){ 94 puts("0"); 95 }else { 96 int k=Query(1,N,1,a); 97 printf("%d ",k); 98 Updata(1,N,1,k,k+a-1,0); 99 } 100 } 101 if (q==2){ 102 scanf("%d%d",&a,&b); 103 Updata(1,N,1,a,a+b-1,1); 104 } 105 } 106 } 107 return 0; 108 }
CodeForces 46D
【题意】：
在长为L的（点0~点L）的线段上停车开车操作；
停车 1 x：车长x，需要b+x+f的空余才能使车停进去，多个区域，选择最左边
开车 2 x：第x次操作，停进的车，开出去
【分析】:
和poj3667很相似，但是处理首位时要特判，同时记录下来第x次操作的车的长度和插入的位置，做插入或更新即可
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #define maxn 110000 5 #define Lson l,m,2*o 6 #define Rson m+1,r,2*o+1 7 #define LL long long 8 using namespace std; 9 int sum[maxn<<2]; 10 int lsum[maxn<<2]; 11 int rsum[maxn<<2]; 12 int col[maxn<<2]; 13 void PushUp(int o,int len){ 14 sum[o]=max(sum[2*o],sum[2*o+1]); 15 sum[o]=max(sum[o],rsum[2*o]+lsum[2*o+1]); 16 lsum[o]=lsum[2*o]; 17 if (lsum[2*o]==len-(len>>1)) lsum[o]+=lsum[2*o+1]; 18 rsum[o]=rsum[2*o+1]; 19 if (rsum[2*o+1]==len>>1) rsum[o]+=rsum[2*o]; 20 return; 21 } 22 void PushDown(int o,int len){ 23 if (col[o]==-1) return;//col==1,表示可以使用 24 col[2*o]=col[2*o+1]=col[o]; 25 sum[2*o]=lsum[2*o]=rsum[2*o]=(len-(len>>1))*col[o]; 26 sum[2*o+1]=rsum[2*o+1]=lsum[2*o+1]= (len>>1)*col[o]; 27 col[o]=-1; 28 return; 29 } 30 void Updata(int l,int r,int o,int L,int R,int x){ 31 if (L<=l && r<=R){ 32 col[o]=x; 33 sum[o]=lsum[o]=rsum[o]=(r-l+1)*x; 34 return ; 35 } 36 PushDown(o,r-l+1); 37 int m=(r+l)>>1; 38 if (L<=m) Updata(Lson,L,R,x); 39 if (m+1<=R) Updata(Rson,L,R,x); 40 PushUp(o,r-l+1); 41 return ; 42 } 43 int Query(int l,int r,int o,int D){ 44 // cout<<"l="<<l<<","<<"r="<<r<<endl; 45 // cout<<"sum="<<sum[o]<<endl; 46 if (l==r) return l; 47 PushDown(o,r-l+1); 48 int m=(l+r)>>1; 49 if (sum[2*o]>=D) return Query(Lson,D); 50 else { 51 if (rsum[2*o]+lsum[2*o+1]>=D){ 52 return m-rsum[2*o]+1; 53 } 54 return Query(Rson,D); 55 } 56 } 57 void BuiltTree(int l,int r,int o){ 58 col[o]=-1; 59 if (l==r){ 60 sum[o]=lsum[o]=rsum[o]=1; 61 return ; 62 } 63 int m=(l+r)>>1; 64 BuiltTree(Lson); 65 BuiltTree(Rson); 66 PushUp(o,r-l+1); 67 return ; 68 } 69 int L,b,f; 70 int px[110]; 71 int py[110]; 72 int main(){ 73 // freopen("out.txt","w",stdout); 74 while(~scanf("%d%d%d",&L,&b,&f)){ 75 int n; 76 scanf("%d",&n); 77 BuiltTree(1,L+b+f,1); 78 for(int i=0;i<n;i++){ 79 int q,a; 80 scanf("%d%d",&q,&a); 81 if (q==1){ 82 // cout<<"sum[1]:"<<sum[1]<<endl; 83 if (sum[1]<a+b+f){ 84 puts("-1"); 85 continue; 86 } 87 int p=Query(1,L+b+f,1,a+b+f); 88 89 p=p+b; 90 printf("%d ",p-b-1); 91 92 // cout<<"p="<<p<<endl; 93 px[i]=p;py[i]=p+a-1; 94 // cout<<"px="<<px[i]<<","<<"py="<<py[i]<<endl; 95 Updata(1,L+b+f,1,px[i],py[i],0); 96 } 97 if (q==2){ 98 Updata(1,L+b+f,1,px[a-1],py[a-1],1); 99 } 100 } 101 } 102 return 0; 103 }
【题意】：算多个矩形的周长并
【分析】：《》
【代码】：
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<stdlib.h> 6 #define Lson l,m,2*o 7 #define Rson m+1,r,2*o+1 8 using namespace std; 9 int maxv[200100<<2]; 10 void updata(int l,int r,int o,int p,int x){ 11 if (l==r){ 12 maxv[o]=x; 13 return ; 14 }else { 15 int m=(l+r)>>1; 16 if (p<=m)updata(Lson,p,x); 17 else updata(Rson,p,x); 18 maxv[o]=max(maxv[2*o],maxv[2*o+1]); 19 } 20 return ; 21 } 22 int h,w,n; 23 void builtTree(int l,int r,int o){ 24 if (l==r) { 25 maxv[o]=w; 26 return ; 27 } 28 int m=(r+l)>>1; 29 builtTree(Lson); 30 builtTree(Rson); 31 maxv[o]=max(maxv[2*o],maxv[2*o+1]); 32 return ; 33 } 34 int Query(int l,int r,int o,int x){ 35 if (l==r){ 36 updata(1,h,1,l,maxv[o]-x); 37 return l; 38 }else { 39 int m=(r+l)>>1; 40 if (maxv[2*o]>=x) return Query(Lson,x); 41 else return Query(Rson,x); 42 } 43 } 44 int main(){ 45 while(~scanf("%d%d%d",&h,&w,&n)){ 46 if (h>n) h=n; 47 builtTree(1,h,1); 48 while(n--){ 49 int x; 50 scanf("%d",&x); 51 if (maxv[1]<x)//没有任何地方可以放 52 { 53 puts("-1"); 54 }else { 55 printf("%d ",Query(1,h,1,x)); 56 } 57 } 58 } 59 return 0; 60 }
【题意】：算多个矩形的面积并
【分析】：《》
【代码】：
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <algorithm> 5 #define Lson l,m,2*o 6 #define Rson m+1,r,2*o+1 7 8 using namespace std; 9 double Y[255];//hash映射 10 double len[255<<2]; 11 int add[255<<2]; 12 int n,cas=0,cnt1,cnt2; 13 int binary(double key){ 14 int l=0,r=cnt1-1; 15 while(l<r){ 16 int m=(l+r)>>1; 17 if (Y[m]==key) return m; 18 if (Y[m]<key) l=m+1; 19 if (Y[m]>key) r=m; 20 } 21 return l; 22 } 23 void PushUp(int o,int l,int r){ 24 if (add[o]>0){ 25 len[o]=Y[r+1]-Y[l]; 26 }else { 27 if (l==r) len[o]=0; 28 else { 29 len[o]=len[o*2]+len[2*o+1]; 30 } 31 } 32 return ; 33 } 34 void Updata(int l,int r,int o,int L,int R,int c){ 35 if (L<=l && r<=R){ 36 add[o]+=c; 37 PushUp(o,l,r); 38 return ; 39 } 40 int m=(r+l)>>1; 41 if (L<=m) Updata(Lson,L,R,c); 42 if (m+1<=R) Updata(Rson,L,R,c); 43 PushUp(o,l,r); 44 return ; 45 } 46 struct Line { 47 double p; 48 double _d,_u; 49 int c; 50 bool operator<(const Line&X)const{ 51 if (p==X.p) return c>X.c; 52 else return p<X.p; 53 } 54 }Lines[255]; 55 int main(){ 56 while(~scanf("%d",&n)&&n){ 57 cas++; 58 cnt1=cnt2=0; 59 for(int i=0;i<n;i++){ 60 double x1,y1,x2,y2; 61 scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 62 Y[cnt1++]=y1;Y[cnt1++]=y2; 63 Lines[cnt2++]=(Line){x1,y1,y2,1}; 64 Lines[cnt2++]=(Line){x2,y1,y2,-1}; 65 } 66 sort(Y,Y+cnt1);//建立i到Y的映射 67 sort(Lines,Lines+cnt2); 68 69 double ans=0; 70 for(int i=0;i<cnt2;i++){ 71 int k1=binary(Lines[i]._d),k2=binary(Lines[i]._u); 72 Updata(0,cnt1,1,k1,k2-1,Lines[i].c); 73 ans+=len[1]*(Lines[i+1].p-Lines[i].p); 74 } 75 printf("Test case #%d ",cas); 76 printf("Total explored area: %.2lf ",ans); 77 } 78 return 0; 79 }