chesed
题意
给你一个长度为 \(n\) 的序列 \(\{ a_i \}\)，有 \(q\) 次询问，每次询问给出 \(l,r,x\)，问初始时数字是 \(x\)，你从 \(l\) 出发，走到 \(r\)，在每个位置进行操作 \(x \gets max(x,a_i-x)\)。问最终的 \(x\) 是多少。
\(n,q \le 2 \times 10^5,|x|,|a_i| \le 10^{13}\)。
思路
观察操作，相当于如果 \(x \le \lfloor \frac{a_i}{2} \rfloor\)，就操作 \(x \gets a_i-x\)。相当于以 \(\lfloor \frac{a_i}{2} \rfloor\) 为对称中心做一个对称。
这种复合函数区间询问题目，我们考虑使用 lxl 老师的《插入-标记-回收》算法。
把询问离线，从左到右扫描 \(a_i\)，遇到一个 \(l_j\) 的时候就插入 \(x_j\)，遇到一个 \(r_j\) 就回收 \(x_j\)。每个 \(a_i\)，对所有还在数据结构中的 \(x\)，将所有 \(\le \lfloor \frac{a_i}{2} \rfloor\) 的 \(x\) 变成 \(x\gets a_i-x\)。
使用什么数据结构呢？每次操作时把一边的 \(x\) 关于对称轴对称过去，相当于取负再加一个 \(tag\)，还需要实时维护 \(x\) 是有序的。这个只能使用平衡树了吧。
平衡树记录三种标记：是否取负，加法 \(tag\)，是否交换左右儿子。这样就可以维护平衡树了。
每次操作，先按照 \(\lfloor \frac{a_i}{2} \rfloor\) 裂成左右两棵平衡树，然后对左边平衡树进行标记的修改，然后合并两棵树。
此时两棵树值域有交叉。
合并平衡树的方式是，把两棵树裂成互相没有值域交集的若干个树，然后类似归并排序的方式合并。
单次合并时间复杂度是 \(O(森林里树的个数 \log)\) 的，或者用题解的话说就是 \(O(段数 \log)\) 的。
一个不是很严谨的证明：考虑我们不希望看到的情况，森林里有 \(n\) 棵树。那么左边和右边分别有 \(\frac{n}{2}\) 棵树，值域刚好一一交错。然后我们 \(O(n\log n)\) 合并它们，发现它们两两之间的距离缩小了一半，因此这样的情况只会有 \(\log V\) 次！然后两两之间没有空隙了，继续合并，时间复杂度就是 \(\log(\frac{n}{2}+\frac{n}{4}+\cdots)=O(n\log^2)\)。
对于插入新的点的情况，你什么时候插它，对总复杂度没有影响吧。
这真是太神奇啦！再思考发现，因为平衡树合并单次复杂度是 \(O(段数\log)\) 的，所以只需要保证合并次数可接受（即前面说的每次两两距离会缩小一半的情况）或者段数缩小速度可以接受（即后面两两间没有空隙的情况），就可以保证时间复杂度啦！
还有个问题，就是如何回收。在操作的时候你会把一个点移动到不知道哪里去了。每个询问对应一个编号，我们记录一下每个点的父亲，这样如果我们要寻找编号为 \(id\) 的点的 \(x\) 是多少，就顺着父亲爬上去，下放标记，然后再返回点的值就好。
时间复杂度 \(O(n\log^2 n)\)。
code
#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
namespace abundant {
constexpr int N=2e5+7;
constexpr ll inf=1e18;
#define isdigit(x) (x>='0'&&x<='9')
#define gc getchar
template <typename T>
void read(T &x) {
x=0;
T fl=1;
char ch=gc();
for(;!isdigit(ch);ch=gc()) if(ch=='-') fl=-1;
for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+(ch^48);
x*=fl;
}
int n,q;
ll a[N],x;
int l,r;
struct pil {
int id;
ll x;
};
vector<pil> vecs[N],vect[N];
int id[N];
ll ans[N];
mt19937 rd(random_device{}());;
struct node {
int rk;
ll val;
int tgmul;
ll tgadd;
int fa,ls,rs;
}tr[N];
int cnt;
int rt;
int newnode(ll val) {
tr[++cnt]={(int)rd(),val,1};
return cnt;
}
void maketag(int u,int mul,ll add) {
if(mul==-1) swap(tr[u].ls,tr[u].rs), tr[u].tgmul*=-1, tr[u].tgadd=add-tr[u].tgadd, tr[u].val=add-tr[u].val;
else tr[u].tgadd+=add, tr[u].val=add+tr[u].val;
}
void pushdown(int u) {
if(!u) return;
if(tr[u].ls) maketag(tr[u].ls,tr[u].tgmul,tr[u].tgadd) ;
if(tr[u].rs) maketag(tr[u].rs,tr[u].tgmul,tr[u].tgadd) ;
tr[u].tgmul=1, tr[u].tgadd=0;
}
void pushup(int u) {
tr[tr[u].ls].fa=u, tr[tr[u].rs].fa=u;
}
void split(int u,int &x,int &y,ll w) {
pushdown(u);
if(!u) x=y=0;
else if(tr[u].val<=w) {
x=u, split(tr[u].rs,tr[u].rs,y,w);
}else {
y=u, split(tr[u].ls,x,tr[u].ls,w);
}
pushup(u);
}
int merge(int x,int y) {
pushdown(x), pushdown(y);
if(!x || !y) return x+y;
if(tr[x].rk<tr[y].rk) {
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}else {
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
ll findmin(int u) {
if(!u) return -inf;
pushdown(u);
if(tr[u].ls) return findmin(tr[u].ls);
return tr[u].val;
}
void change(int u,ll x) {
maketag(u,-1,x);
}
int _merge(int x,int y) {
if(!x || !y) return x+y;
int s=0;
int _x,_y;
ll mnx=findmin(x),mny=findmin(y);
if(mnx>mny) swap(x,y),swap(mnx,mny);
while(1) {
split(x,_x,_y,mny);
s=merge(s,_x);
x=_y;
if(!x) return merge(s,y);
mnx=findmin(x);
if(mnx>mny) swap(x,y),swap(mnx,mny);
}
}
void getans(int u) {
if(u!=rt) getans(tr[u].fa);
pushdown(u);
}
void main() {
read(n),read(q);
rep(i,1,n) read(a[i]);
rep(i,1,q) {
read(x),read(l),read(r);
vecs[l].push_back({i,x}), vect[r].push_back({i,x});
}
rep(i,1,n) {
for(auto u : vecs[i]) {
int x,y,z=id[u.id]=newnode(u.x);
split(rt,x,y,u.x);
rt=merge(x,merge(z,y));
}
int x,y;
split(rt,x,y,a[i]>>1);
change(x,a[i]);
rt=_merge(x,y);
for(auto u : vect[i]) {
int p=id[u.id];
getans(p);
ans[u.id]=tr[p].val;
}
}
rep(i,1,q) pf("%lld\n",ans[i]) ;
}
}
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#endif
abundant :: main();
}