【UVa】11983 Weird Advertisement

  1 #include<cstdio>
  2 #include<algorithm>
  3 typedef long long LL;
  4 #define MAXN 30010
  5 using namespace std;
  6 int n,k;
  7 struct Seg
  8 {
  9     int left,right,high,flag;
 10     friend bool operator<(Seg a,Seg b)
 11     {
 12         if(a.high==b.high)
 13             return a.flag<b.flag;
 14         return a.high<b.high;
 15     }
 16 };
 17 struct node
 18 {
 19     int cover,dp[11];
 20 };
 21 node tree[MAXN<<3];
 22 Seg p[MAXN<<1];
 23 int X[MAXN<<1];
 24 void Build(int L,int R,int rt)
 25 {
 26     int i;
 27     for(tree[rt].cover=i=0;i<=k;i++)
 28         tree[rt].dp[i]=0;
 29     if(L!=R)
 30     {
 31         int mid=(L+R)>>1;
 32         Build(L,mid,rt<<1);
 33         Build(mid+1,R,rt<<1|1);
 34     }
 35 }
 36 void PushUp(int L,int R,int rt)
 37 {
 38     int i;
 39     if(tree[rt].cover)
 40     {
 41         for(i=1;i<=k;i++)
 42         {
 43             if(tree[rt].cover>=i)
 44                 tree[rt].dp[i]=X[R+1]-X[L];
 45             else if(L==R)
 46                 tree[rt].dp[i]=0;
 47             else
 48                 tree[rt].dp[i]=tree[rt<<1].dp[i-tree[rt].cover]+tree[rt<<1|1].dp[i-tree[rt].cover];
 49         }
 50     }
 51     else
 52     {
 53         for(i=1;i<=k;i++)
 54         {
 55             if(L!=R)
 56                 tree[rt].dp[i]=tree[rt<<1].dp[i]+tree[rt<<1|1].dp[i];
 57             else
 58                 tree[rt].dp[i]=0;
 59         }
 60     }
 61 }
 62 void Update(int x,int y,int flag,int L,int R,int rt)
 63 {
 64     if(x<=L&&R<=y)
 65     {
 66         tree[rt].cover+=flag;
 67         PushUp(L,R,rt);
 68     }
 69     else
 70     {
 71         int mid=(L+R)>>1;
 72         if(x<=mid)
 73             Update(x,y,flag,L,mid,rt<<1);
 74         if(y>mid)
 75             Update(x,y,flag,mid+1,R,rt<<1|1);
 76         PushUp(L,R,rt);
 77     }
 78 }
 79 int main()
 80 {
 81     LL ans;
 82     int t,ca=1;
 83     int i,x1,y1,x2,y2,cnt;
 84     scanf("%d",&t);
 85     while(t--)
 86     {
 87         scanf("%d%d",&n,&k);
 88         for(ans=cnt=i=0;i<n;i++)
 89         {
 90             scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
 91             x2++;
 92             y2++;
 93             p[cnt].left=x1;
 94             p[cnt].right=x2;
 95             p[cnt].high=y1;
 96             p[cnt].flag=1;
 97             X[cnt++]=x1;
 98             p[cnt]=p[cnt-1];
 99             p[cnt].high=y2;
100             p[cnt].flag=-1;
101             X[cnt++]=x2;
102         }
103         sort(X,X+cnt);
104         sort(p,p+cnt);
105         n=unique(X,X+cnt)-X;
106         Build(0,n-2,1);
107         for(i=0;i<cnt;i++)
108         {
109             x1=lower_bound(X,X+n,p[i].left)-X;
110             y1=lower_bound(X,X+n,p[i].right)-X;
111             Update(x1,y1-1,p[i].flag,0,n-2,1);
112             if(i+1<cnt)
113                 ans+=(p[i+1].high-p[i].high)*(LL)tree[1].dp[k];
114         }
115         printf("Case %d: %lld\n",ca++,ans);
116     }
117     return 0;
118 }
新博客：www.zhixiangli.com