题解 AT2441 【断層 (Geologic Fault)】
来自P5103的题解 这题关键在于逆向思维，就是考虑最后的nn的个点刚开始在哪儿，这样就减少了很多需要维护的东西。 这就让我想到很久以前的一道NOIP题，铺地毯。那是我第一次接触逆向思维，觉得十分的巧妙，原本要写的很麻烦或者干脆写不出来的题，反着想，竟然几行就完事了。
不扯别的了，还是说一下这题怎么想吧……
把操作离线，然后倒着操作，上移变成了下移。但是每一次移动两维的坐标都会改变，十分的难受。于是我们把坐标轴旋转45度，就十分美滋滋了：以顺时针举例，如果斜率为1，在新的坐标系中只有纵坐标发生了改变；斜率为-1，只有横坐标发生了改变。而且改变的这些点一定是一个前缀或者后缀。于是更新可用线段树实现。
不过更为重要的是，对于查询的nn个点，无论逆向怎么操作，这些点的横、纵坐标的相对大小都不会变，大的只会更大，小的只会更小。
有了这个性质，我们就可以二分找要改的前缀（后缀）的边界了。判断的时候就是线段树单点查询。
到这里这题基本就完事了，需要注意的是，区间修改时应该加（减）的是2l2l，因为在原本的坐标系中移动的距离是\sqrt{2} l 2 l，而新坐标系的距离又是原来的\sqrt{2} 2 倍，所以应该是\sqrt{2} * \sqrt{2}l 2 ∗ 2 l。
线段树有点慢，需要开O2才能过，改成树状数组就快很多了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define space putchar(' ')
#define enter puts("")
#define Mem(a, x) memset(a, x, sizeof(x))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 4e5 + 5;
const int N = 262144;
In ll read()
{
ll ans = 0;
char ch = getchar(), las = ' ';
while(!isdigit(ch)) las = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(las == '-') ans = -ans;
return ans;
}
In void write(ll x)
{
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, Q;
struct Que
{
int d; ll x, l;
}q[maxn];
struct Tree
{
int l[maxn << 2], r[maxn << 2];
ll lzy[maxn << 2];
In void build(int L, int R, int now, int flg)
{
l[now] = L; r[now] = R;
if(L == R) {lzy[now] = L * flg; return;}
int mid = (L + R) >> 1;
build(L, mid, now << 1, flg);
build(mid + 1, R, now << 1 | 1, flg);
}
In void pushdown(int now)
{
if(lzy[now])
{
lzy[now << 1] += lzy[now]; lzy[now << 1 | 1] += lzy[now];
lzy[now] = 0;
}
}
In void update(int L, int R, int now, int d)
{
if(l[now] == L && r[now] == R)
{
lzy[now] += d;
return;
}
pushdown(now);
int mid = (l[now] + r[now]) >> 1;
if(R <= mid) update(L, R, now << 1, d);
else if(L > mid) update(L, R, now << 1 | 1, d);
else update(L, mid, now << 1, d), update(mid + 1, R, now << 1 | 1, d);
}
In ll query(int now, int id)
{
if(l[now] == r[now]) return lzy[now];
pushdown(now);
int mid = (l[now] + r[now]) >> 1;
if(id <= mid) return query(now << 1, id);
else return query(now << 1 | 1, id);
}
}t1, t2;
int main()
{
n = read(), Q = read();
for(int i = Q; i; --i) q[i].x = read(), q[i].d = read(), q[i].l = read();
t1.build(0, N - 1, 1, 1), t2.build(0, N - 1, 1, -1);
for(int i = 1; i <= Q; ++i)
{
if(q[i].d == 1)
{
int L = 0, R = N - 1;
while(L < R)
{
int mid = ((L + R) >> 1) + 1;
if(t2.query(1, mid) < -q[i].x) R = mid - 1;
else L = mid;
}
t1.update(0, L, 1, -q[i].l * 2);
}
else
{
int L = 0, R = N - 1;
while(L < R)
{
int mid = ((L + R) >> 1) + 1;
if(t1.query(1, mid) > q[i].x) R = mid - 1;
else L = mid;
}
if(L + 1 > N - 1) --L;
t2.update(L + 1, N - 1, 1, -q[i].l * 2);
}
}
for(int i = 1; i <= n; ++i) write(-(t2.query(1, i) + t1.query(1, i)) / 2), enter;
return 0;
}