Codeforces Round #310 (Div. 1) C. Case of Chocolate (线段树)

本文主要是介绍Codeforces Round #310 (Div. 1) C. Case of Chocolate (线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：传送门
这题虽然是DIV1的C。。但是挺简单的。。只要用线段树分别维护一下横着和竖着的值就可以了，先离散化再维护。每次查找最大的最小值<=tmp的点，可以直接在线段树里搜，也可以二分去找。
代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
#include <time.h>
using namespace std;
#define LL __int64
#define pi acos(-1.0)
//#pragma comment(linker, "/STACK:1024000000")
#define root 0, cnt-1, 1
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
const int MAXN=400000+10;
int a[MAXN], c[MAXN], cnt, ha[MAXN];
int Min[2][MAXN<<2];
struct node
{int x, y, f;
}fei[MAXN];
void PushUp(int f, int rt)
{Min[f][rt]=min(Min[f][rt<<1],Min[f][rt<<1|1]);
}
void Update(int f, int p, int x, int l, int r, int rt)
{if(l==r){Min[f][rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(f,p,x,lson);else Update(f,p,x,rson);PushUp(f,rt);
}
int seach(int f, int rr, int x, int l, int r, int rt)
{if(l==r){if(Min[f][rt]<=x) return l;return -1;}int ans=-1, mid=l+r>>1;if(rr>mid&&Min[f][rt<<1|1]<=x) ans=seach(f,rr,x,rson);if(ans!=-1) return ans;if(Min[f][rt<<1]<=x) ans=seach(f,rr,x,lson);return ans;
}
int BS(int x)
{int low=0, high=cnt-1, mid;while(low<=high){mid=low+high>>1;if(c[mid]==x) return mid;else if(c[mid]>x) high=mid-1;else low=mid+1;}
}
int main()
{int n, q, i, j, x, y, tmpx, tmpy, z;char ch[3];while(scanf("%d%d",&n,&q)!=EOF){for(i=0;i<q;i++){scanf("%d%d",&fei[i].x,&fei[i].y);scanf("%s",ch);if(ch[0]=='U'){a[i<<1]=fei[i].x;a[i<<1|1]=fei[i].y;fei[i].f=0;}else{a[i<<1]=fei[i].x;a[i<<1|1]=fei[i].y;fei[i].f=1;}}memset(ha,0,sizeof(ha));sort(a,a+2*q);c[0]=a[0];cnt=1;for(i=1;i<2*q;i++){if(a[i]!=a[i-1]){c[cnt++]=a[i];}}memset(Min,INF,sizeof(Min));for(i=0;i<q;i++){tmpx=BS(fei[i].x);tmpy=BS(fei[i].y);if(ha[tmpx]){puts("0");continue ;}ha[tmpx]=1;if(fei[i].f){if(tmpx==0){printf("%d\n",fei[i].x);Update(0,tmpy,0,root);continue ;}z=seach(1,tmpx,tmpy,root);if(z==-1){printf("%d\n",fei[i].x);Update(0,tmpy,0,root);continue ;}printf("%d\n",fei[i].x-c[z]);Update(0,tmpy,z+1,root);}else{if(tmpy==0){printf("%d\n",fei[i].y);Update(1,tmpx,0,root);continue ;}z=seach(0,tmpy,tmpx,root);if(z==-1){printf("%d\n",fei[i].y);Update(1,tmpx,0,root);continue ;}printf("%d\n",fei[i].y-c[z]);Update(1,tmpx,z+1,root);}}}return 0;
}