【扫描线或树状数组】CSU 1335 高桥和低桥

http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1335

【题意】

• 给定n座桥的高度，给定m次洪水每次的涨水水位ai和退水水位bi
• 询问有多少座桥被淹的次数大于等于k
• 洪水最开始的水位为1

【思路】

• 每座桥被淹一次是这样的：开始时的水位小于桥的高度，洪水最高点的水位不小于桥的高度，如有一座高度为5的桥，对于数据7 6和7 3被淹的次数都是1（看5在不在(1,7]的区间内）
• 把n座桥排序，每次洪水都有一个区间的桥被淹，问最后每座桥被淹多少次
• 这就是裸的扫描线，或者树状数组区间修改单点查询也可以

【AC】

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int a[maxn];

 int n,m,k;

 int f[maxn];

 void init()

 {

     memset(f,,sizeof(f));

 }

 int main()

 {

     int cas=;

     while(~scanf("%d%d%d",&n,&m,&k))

     {

         init();

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

         }

         sort(a+,a+n+);

         int x,y;

         int st=,ed;

         for(int i=;i<=m;i++)

         {

             scanf("%d%d",&x,&y);

             ed=x;

             int pos1=upper_bound(a+,a++n,st)-a;

             int pos2=upper_bound(a+,a++n,ed)-a-;

             f[pos1]++;

             f[pos2+]--;

             st=y;

         }

         int ans=;

         int s=;

         for(int i=;i<=n;i++)

         {

             s+=f[i];

             if(s>=k) ans++;

         }

         printf("Case %d: %d\n",++cas,ans);

     }

     return ;

 }

扫描线

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int a[maxn];

 int tree[maxn];

 int n,m,k;

 int lowbit(int x)

 {

     return x&(-x);

 }

 void add(int k,int x)

 {

     while(k<=n)

     {

         tree[k]+=x;

         k+=lowbit(k);

     }

 }

 int query(int k)

 {

     int res=;

     while(k)

     {

         res+=tree[k];

         k-=lowbit(k);

     }

     return res;

 }

 void init()

 {

     memset(tree,,sizeof(tree));

 }

 int main()

 {

     int cas=;

     while(~scanf("%d%d%d",&n,&m,&k))

     {

         init();

         for(int i=;i<=n;i++)

         {

             scanf("%d",&a[i]);

         }

         sort(a+,a+n+);

         int x,y;

         int st=,ed;

         for(int i=;i<=m;i++)

         {

             scanf("%d%d",&x,&y);

             ed=x;

             int pos1=upper_bound(a+,a++n,st)-a;

             int pos2=upper_bound(a+,a++n,ed)-a-;

             add(pos1,);

             add(pos2+,-);

             st=y;

         }

         int ans=;

         for(int i=;i<=n;i++)

         {

             if(query(i)>=k)

             {

                 ans++;

             }

         }

         printf("Case %d: %d\n",++cas,ans);

     }

     return ;

 }

树状数组区间修改单点查询