题解：P11622 [Ynoi Easy Round 2025] TEST_176

· · 题解

插入标记回收板子。

将询问离线，用一颗值域上的平衡树维护，做扫描线，对于一个形如 [l,r,x] 的询问，在扫到 l 时将 x 插入，在扫完 r 时将其回收。

然后进行操作，假如当前扫到了 i，那么就是将平衡树中小于 \left\lfloor\frac{a_i}{2}\right\rfloor 的乘上 -1 再加上 a_i，其余的不变。然后再将平衡树合并起来，用到值域有交平衡树合并。

对于回收时，特别地，记录一下平衡树每个节点的父亲，回收时将其到根的链提出来，然后从顶往下 pushdown 即可。

本题的一些细节：

  1. 开 long long。
  2. 打区间乘 -1 标记时，记得交换左右儿子。
  3. 平衡树合并时，合并权值相同的节点，否则复杂度时错误的。
  4. 只要平衡树合并复杂度正确，本题就不怎么卡常。
#include<bits/stdc++.h>
using namespace std;
namespace IO {
#ifdef LOCAL
  FILE*Fin(fopen("in.in","r")),*Fout(fopen("out.out","w"));
#else
  FILE*Fin(stdin),*Fout(stdout);
#endif
  class qistream{static const size_t SIZE=1<<16,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qistream(FILE*_fp=stdin):fp(_fp),p(0){fread(buf+p,1,SIZE-p,fp);}void flush(){memmove(buf,buf+p,SIZE-p),fread(buf+SIZE-p,1,p,fp),p=0;}qistream&operator>>(char&x){x=getch();while(isspace(x))x=getch();return*this;}template<class T>qistream&operator>>(T&x){x=0;p+BLOCK>=SIZE?flush():void();bool flag=false;for(;!isdigit(buf[p]);++p)flag=buf[p]=='-';for(;isdigit(buf[p]);++p)x=x*10+buf[p]-'0';x=flag?-x:x;return*this;}char getch(){p+BLOCK>=SIZE?flush():void();return buf[p++];}qistream&operator>>(char*str){char ch=getch();while(ch<=' ')ch=getch();int i=0;for(;ch>' ';++i,ch=getch())str[i]=ch;str[i]='\0';return*this;}}qcin(Fin);
  class qostream{static const size_t SIZE=1<<16,BLOCK=64;FILE*fp;char buf[SIZE];int p;public:qostream(FILE*_fp=stdout):fp(_fp),p(0){}~qostream(){fwrite(buf,1,p,fp);}void flush(){fwrite(buf,1,p,fp),p=0;}template<class T>qostream&operator<<(T x){int len=0;p+BLOCK>=SIZE?flush():void();x<0?(x=-x,buf[p++]='-'):0;do buf[p+len]=x%10+'0',x/=10,++len;while(x);for(int i=0,j=len-1;i<j;++i,--j)std::swap(buf[p+i],buf[p+j]);p+=len;return*this;}qostream&operator<<(char x){putch(x);return*this;}void putch(char ch){p+BLOCK>=SIZE?flush():void();buf[p++]=ch;}qostream&operator<<(char*str){for(int i=0;str[i];++i)putch(str[i]);return*this;}qostream&operator<<(const char*s){for(int i=0;s[i];++i)putch(s[i]);return*this;}}qcout(Fout);
}
using ll = long long;
const int N = 2e5 + 10,M = 2e5 + 10;
int n,m,p,tid[M],st[100],idx[M]; ll ans[M],a[N];
int Find(int x) { return x == idx[x] ? x : idx[x] = Find(idx[x]); }
mt19937 rd(24320);
vector<int> De[N];
vector<pair<int,ll> > Ad[N];
struct node{ int ls,rs,cn,siz,fa,pri; ll val,lz1,lz2; } t[M];
#define ls(x) t[x].ls
#define rs(x) t[x].rs
#define cn(x) t[x].cn
#define siz(x) t[x].siz
#define fa(x) t[x].fa
#define pri(x) t[x].pri
#define val(x) t[x].val
#define lz1(x) t[x].lz1
#define lz2(x) t[x].lz2
int tot,rt;
inline int New(ll val){t[++tot] = {0,0,1,1,0,(int)rd(),val,0,1}; return idx[tot]=tot;}
inline void P(int p){
  siz(p) = siz(ls(p)) + siz(rs(p)) + cn(p);
  fa(p) = 0;
  if(ls(p)) fa(ls(p)) = p;
  if(rs(p)) fa(rs(p)) = p;
}
inline void mk1(int p,ll val){if(p) val(p) += val,lz1(p) += val;}
inline void mk2(int p,ll val){if(p) val(p) *= -1,lz1(p) *= -1,lz2(p) *= -1;}
inline void D(int p){
  if(lz2(p) != 1) mk2(ls(p),lz2(p)),mk2(rs(p),lz2(p)),swap(ls(p),rs(p)),lz2(p) = 1;
  if(lz1(p)) mk1(ls(p),lz1(p)),mk1(rs(p),lz1(p)),lz1(p) = 0;
}
void split(int p,ll val,int &x,int &y){
  if(!p) return x = y = 0,void();
  D(p);
  if(val(p) <= val) x = p,split(rs(p),val,rs(x),y);
  else y = p,split(ls(p),val,x,ls(y));
  P(p);
}
int Merge(int x,int y){
  if(!x || !y) return x|y;
  if(pri(x) < pri(y)) return D(x),rs(x) = Merge(rs(x),y),P(x),x;
  else return D(y),ls(y) = Merge(x,ls(y)),P(y),y;
}
int Join(int x, int y) { // x <- y
  if (!x || !y) return x | y; // 有一个空的即可返回
  if (pri(x) > pri(y)) swap(x, y); // 取随机权值小的作为根
  D(x);D(y);
  int L1 = ls(x), R1 = rs(x), L2 = 0, R2 = 0, equ = 0; // x 直接是左右子树
  split(y, val(x), L2, R2), split(L2, val(x) - 1, L2, equ); // y 按权值 split
  if (equ) cn(x) += siz(equ), siz(x) += siz(equ), idx[equ] = x; // 相等特殊处理
  ls(x) = Join(L1, L2), rs(x) = Join(R1, R2); // 递归合并
  return P(x), x; // 更新信息
}
inline int Insert(ll v) {
  int pl = 0, pm = 0, pr = 0;
  split(rt, v, pl, pr), split(pl, v - 1, pl, pm);
  pm ? (++cn(pm), ++siz(pm)) : pm = New(v);
  return rt = Merge(Merge(pl, pm), pr), pm;
}
inline ll get(int id){
  int num = 0;
  for(;id && (st[++num] = id);id = fa(id));
  if (int y = Find(st[num]); y != st[num])
    for (id = y, num = 0;id && (st[++num] = id);id = fa(id));
  for (int i = num; i > 1; D(st[i--]));
  return val(st[1]);
}
inline void upd(ll val){
  int x = 0,y = 0;
  split(rt,floor(val/2.0),x,y);
  mk2(x,-1);mk1(x,val);
  rt = Join(x,y);
}
void print(int x){
  D(x);
  cerr<<x<<": "<<val(x)<<' '<<fa(x)<<'\n';
  if(ls(x)) print(ls(x));
  if(rs(x)) print(rs(x));
}
signed main(){
  //cin.tie(nullptr)->sync_with_stdio(false);
  IO::qcin>>n>>m;
  for (int i = 1; i <= n; i++) IO::qcin>>a[i];
  for (int i = 1, l, r; i <= m; i++) {
    ll x;
    IO::qcin>>x>>l>>r;
    Ad[l].emplace_back(i,x);
    De[r].emplace_back(i);
  }
  for (int i = 1; i <= n; i++) {
    for(auto &[id,x]:Ad[i]) tid[id] = Insert(x);
    upd(a[i]);
    for(int &id:De[i]) ans[id] = get(tid[id]);
    //cerr<<i<<":::\n";
    //print(rt);
    //cerr<<"\n";
  }
  for (int i = 1; i <= m; i++)
    IO::qcout<<ans[i]<<'\n';
}