传送门：点击打开链接
题意：阶梯形的巧克力，每次选择边缘的一个格子，然后向上吃或者向左吃，直到边界或者空白位置停止，吃过的位置之后就是空白。
思路：n很大，先把q查询的那些位置离散化一下，注意x+1和y+1也需要离散化一下。
之后y会限制后来的x，x会限制后来的y，搞两个分开的线段树分别维护x和y就行了
还要弄个vis来判断某一行或某一列是否已经放过，就ok了
总的来说只要想清楚了细节，不难处理
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <string>
#include <vector>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 4e5 + 5;
char op[MX][2];
int n, q, xsz, ysz;
int X[MX], Y[MX], BX[MX], BY[MX];
int MAX[2][MX << 2], col[2][MX << 2];
int visx[MX], visy[MX];
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1int bsx(int x) {return lower_bound(BX + 1, BX + 1 + xsz, x) - BX;
}
int bsy(int x) {return lower_bound(BY + 1, BY + 1 + ysz, x) - BY;
}
void push_up(int z, int rt) {MAX[z][rt] = max(MAX[z][rt << 1], MAX[z][rt << 1 | 1]);
}
void upset(int z, int rt, int c) {MAX[z][rt] = max(MAX[z][rt], c);col[z][rt] = max(col[z][rt], c);
}
void push_down(int z, int rt) {if(col[z][rt]) {upset(z, rt << 1, col[z][rt]);upset(z, rt << 1 | 1, col[z][rt]);col[z][rt] = 0;}
}
int query(int z, int p, int l, int r, int rt) {if(l == r) {return MAX[z][rt];}int m = (l + r) >> 1;push_down(z, rt);if(p <= m) return query(z, p, lson);else return query(z, p, rson);
}
void update(int z, int L, int R, int x, int l, int r, int rt) {if(L <= l && r <= R) {upset(z, rt, x);return;}int m = (l + r) >> 1;push_down(z, rt);if(L <= m) update(z, L, R, x, lson);if(R > m) update(z, L, R, x, rson);push_up(z, rt);
}int main() {//FIN;scanf("%d%d", &n, &q);for(int i = 1; i <= q; i++) {scanf("%d%d%s", &X[i], &Y[i], op[i]); swap(X[i], Y[i]);BX[++xsz] = X[i]; BX[++xsz] = X[i] + 1;BY[++ysz] = Y[i]; BY[++ysz] = Y[i] + 1;}sort(BX + 1, BX + 1 + xsz); xsz = unique(BX + 1, BX + 1 + xsz) - BX - 1;sort(BY + 1, BY + 1 + ysz); ysz = unique(BY + 1, BY + 1 + ysz) - BY - 1;for(int i = 1; i <= q; i++) {if(op[i][0] == 'L') {if(visx[bsx(X[i])]) {printf("0\n");continue;}visx[bsx(X[i])] = 1;int t = query(0, bsx(X[i]), 1, xsz, 1);update(1, bsy(t + 1), bsy(Y[i]), X[i], 1, ysz, 1);printf("%d\n", Y[i] - t);} else {if(visy[bsy(Y[i])]) {printf("0\n");continue;}visy[bsy(Y[i])] = 1;int t = query(1, bsy(Y[i]), 1, ysz, 1);update(0, bsx(t + 1), bsx(X[i]), Y[i], 1, xsz, 1);printf("%d\n", X[i] - t);}}return 0;
}