题解 UVA12663 【High bridge, low bridge】

题目大意：给n个桥，m次潮涨落，给定潮涨落的高度，问被淹没次数大于等于k的桥的个数，对于一直被淹没的，只记录一次。 把不同高度的桥看做坐标不同的点，然后潮涨落就相当于一次区间修改 修改的是上次潮落位置+1的桥到本次潮涨的位置，输出答案时需要访问到每个叶子结点。 AC代码 ```cpp #include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define ls k<<1 #define rs k<<1|1 #define lson k<<1,l,mid #define rson k<<1|1,mid+1,r #define mid ((l+r)>>1) #define laz(rt) tr[rt].laz #define sum(rt) tr[rt].sum const int maxn=100101; int a[maxn]; int ki,cnt,n,m; struct node{ int sum,laz; }tr[maxn<<2]; inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } inline void down(int k){ sum(ls)+=laz(k);sum(rs)+=laz(k); laz(ls)+=laz(k);laz(rs)+=laz(k); laz(k)=0; } void build(int k,int l,int r){ laz(k)=sum(k)=0; if(l==r)return ; build(lson);build(rson); } void change(int k,int l,int r,int x,int y,int v){ if(x<=l&&y>=r){ laz(k)+=v;sum(k)+=v; return ; } if(laz(k))down(k); if(x<=mid)change(lson,x,y,v); if(y>mid)change(rson,x,y,v); } int ask(int k,int l,int r){ if(l==r) return sum(k)>=ki; if(laz(k))down(k); return ask(lson)+ask(rson); } int c[maxn],d[maxn],x,y; int main(){ while(scanf("%d%d%d",&n,&m,&ki)!=EOF){ for(int i=1;i<=n;i++) a[i]=read(); sort(a+1,a+n+1); build(1,1,n); d[0]=0; for(int i=1;i<=m;i++){ c[i]=read();d[i]=read(); x=lower_bound(a+1,a+n+1,d[i-1]+1)-a; y=upper_bound(a+1,a+n+1,c[i])-a; if(a[y]>c[i])y--; change(1,1,n,x,y,1); } printf("Case %d: %d\n",++cnt,ask(1,1,n)); } return 0; } ```