本文主要是介绍【CF】C. Glass Carving（二分 + 树状数组 + 优先队列 + 数组计数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题简直蛋疼死。。。。。
A了一下午
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 200005;
int h,w,n;
int C1[maxn],C2[maxn];
int vis1[maxn] = {0},vis2[maxn] = {0};
priority_queue<int,vector<int>,less<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;
int lowbit(int x){return x & -x;
}
int sum(int C[],int x){int ret = 0;while(x > 0){ret += C[x];x -= lowbit(x);}return ret;
}
void add(int x,int d,int n,int C[]){while(x <= n){C[x] += d;x += lowbit(x);}
}
int main(){memset(C1,0,sizeof(C1));memset(C2,0,sizeof(C2));scanf("%d%d%d",&w,&h,&n);int max_width = w;int max_height = h;int oh = 0, ow = 0;vis1[h] ++; q1.push(h);vis2[w] ++; q2.push(w);h ++;w ++;add(1,1,h,C1); add(h,1,h,C1);add(1,1,w,C2); add(w,1,w,C2);for(int i = 0; i < n; i++){char str[7];int d;scanf("%s%d",str,&d);d ++;if(str[0] == 'H'){int l = 1,r = d - 1;int e1,e2;int v = sum(C1,d);while(l < r){int mid = (l + r) >> 1;int ans = sum(C1,mid);if(ans >= v)r = mid;elsel = mid + 1;}e1 = l;add(d,1,h,C1);v = sum(C1,d) + 1;l = d + 1;r = h;while(l < r){int mid = (l + r) >> 1;int ans = sum(C1,mid);if(ans < v)l = mid + 1;elser = mid;}e2 = l;int d1 = d - e1,d2 = e2 - d;vis1[d1 + d2]--;if(!vis1[d1]) q1.push(d1);if(!vis1[d2]) q1.push(d2);vis1[d1] ++;vis1[d2] ++;while(!q1.empty()){int t = q1.top(); q1.pop();if(vis1[t]){max_height = t;q1.push(t);break;}}}else if(str[0] == 'V'){int l = 1,r = d - 1;int e1,e2;int v = sum(C2,d);while(l < r){int mid = (l + r) >> 1;int ans = sum(C2,mid);if(ans < v)l = mid + 1;elser = mid;}e1 = l;add(d,1,w,C2);v = sum(C2,d) + 1;l = d + 1;r = w;while(l < r){int mid = (l + r) >> 1;int ans = sum(C2,mid);if(ans < v)l = mid + 1;elser = mid;}e2 = l;int d1 = d - e1,d2 = e2 - d;vis2[d1 + d2]--;if(!vis2[d1]) q2.push(d1);if(!vis2[d2]) q2.push(d2);vis2[d1] ++;vis2[d2] ++;while(!q2.empty()){int t = q2.top(); q2.pop();if(vis2[t]){max_width = t;q2.push(t);break;}}}printf("%I64d\n",(LL)max_width * max_height);}return 0;
}
这篇关于【CF】C. Glass Carving（二分 + 树状数组 + 优先队列 + 数组计数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
