[Ynoi2010] y-fast trie
思路
考虑在插入所有元素的时候对 \(C\) 取模。
那么可以分类讨论了:
- \(0\leq x+y<C\)
- \(x+y\geq C\)
考虑第二种情况等价于取集合中前两大的数,可以简单维护。
考虑第一种情况,对于一个数 \(x\) 令 \(f(x)\) 为小于 \(C-1-x\) 的最大的数,那么就可以套路维护 \(n\) 个元素对 \((x,f(x))\)。那么在插入 \(x\) 的时候可以平衡树找到 \(f(x)\),问题变为小于某值的最大值。
而有些数的 \(f(y)=x\),而这样的 \(y\) 最劣情况下复杂度是 \(\mathcal O(n)\) 的,这时候如果对集合中的每个数暴力重构 \(f\) 时间就错了。
我们设 \(nxt_x\) 为 \(x\) 的后继,考虑什么数可以让 \(x\) 作为自己的 \(f\),那么这些数必定小于等于 \(C-1-x\),而如果这个数小到一定程度,那么就可以让 \(nxt_x\) 作为自己的 \(f\) 了,所以以 \(x\) 为 \(f\) 的数在数轴上应该在区间 \((C-1-nxt_x, C-1,x]\) 之间,那么这个操作等价于平衡树上的区间覆盖,可以单 \(log\) 维护。
考虑删除操作,我们可以套路线段树分治把删除操作变为撤销操作,离线 \(\mathcal O(n\log^2 n)\),那么这道题就做完了。
考虑强制在线,我们观察删除一个数 \(x\) 的时候,哪些数 \(f(y)=x\)。设 \(pre_x\) 为 \(x\) 的前驱,那么本来以 \(x\) 作为 \(f\) 的数在区间 \((C-1-nxt_x, C-1,x]\) 中,但现在需要删除 \(x\) ,而这些数又不能让 \(nxt_x\) 作为自己的 \(f\) ,所以需要让 \(pre_x\) 对区间 \((C-1-nxt_x,C-1-pre_x]\) 作一次区间覆盖。
细节:
- \(x\) 互不相同,但是 \(x\%C\) 可能有重复的,因此需要开
multiset
。 - \(x\) 不能作为自己的 \(f(x)\),但是如果 \(x\) 有两个及以上则可以。这部分的解决方法是在插入的时候先更新 \(f\) 再插入 \(x\),删除的时候令 \(pre_x,nxt_x=x\) 即可。
复杂度是 \(\mathcal O(n\log n)\) 的,能不能 1s 过看使用的平衡树的常数,毕竟笔者由于 \(5e5\) 的数据范围和本人优秀的写法 \(fhq\_treap\) 的巨大常数,因此不得不让 lxl 把洛谷上的时限开到了 2s 还好有后台能改时限。
code
#include <bits/stdc++.h>
#define mk make_pair
#define pb push_back
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 10;
const int INF = 0x3f3f3f3f;
typedef pair <int, int> pii;
char buf[1 << 23],*p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
int x = 0; char ch = getchar ();
while (ch < '0' || ch > '9') { ch = getchar (); }
while (ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar ();
return x;
}
void print(int x) {
if(x > 9) print(x / 10);
*O++ =x % 10 +'0';
}
int n, C, seed = 114514;
int root;
multiset <int> s;
set <int> :: iterator it, mx1;
inline int Rand() { return (seed = (seed << 21) + (seed >> 3)); }
inline int Max(int x, int y) { return (x > y) ? x : y; }
int node;
int x, y, z, Pre, Nxt;
struct node {
int ls, rs;
int key, siz, val;
int cov, tag, mv, mx;
} t[N];
inline void pushup (int x)
{
t[x].siz = t[t[x].ls].siz + t[t[x].rs].siz + 1;
t[x].mv = Max (Max (t[t[x].ls].mv, t[t[x].rs].mv), t[x].val); // mv 是区间最大值
t[x].mx = Max (Max (t[t[x].ls].mx, t[t[x].rs].mx), t[x].val + t[x].cov); // mx 是区间最大的 pair 值
}
#define Cov(now,v) t[now].tag = t[now].cov = (v), t[now].mx = (v) + t[now].mv;
inline void pushdown (int x)
{
if (~t[x].tag)
{
if (t[x].ls) Cov (t[x].ls, t[x].tag);
if (t[x].rs) Cov (t[x].rs, t[x].tag);
t[x].tag = -1;
}
}
inline int merge (int x, int y)
{
if (!x || !y) return x + y;
pushdown(x), pushdown(y);
if (t[x].key < t[y].key) { t[x].rs = merge (t[x].rs, y); pushup (x); return x; }
else { t[y].ls = merge (x, t[y].ls); pushup (y); return y; }
}
inline void split (int now, int k, int &x, int &y)
{
if (!now) { x = y = 0; return ; }
pushdown (now);
if (t[now].val <= k) x = now, split (t[now].rs, k, t[x].rs, y);
else y = now, split (t[now].ls, k, x, t[y].ls);
pushup (now);
}
inline int new_node (register int v, register int v1)
{
t[++node].siz = 1;
t[node].key = Rand ();
t[node].val = t[node].mv = v;
t[node].tag = -1; t[node].cov = v1;
t[node].mx = v + v1;
return node;
}
inline void cover (register int l, register int r, register int c)
{
split (root, l - 1, x, y);
split (y, r, y, z);
if(y) Cov(y, c);
root = merge (merge (x, y), z);
}
inline void update (register int v)
{
it = s.upb (C - 1 - v); it--;
if (*it == v) it--;
cover (v, v, *it);
}
inline void insert (int v, int v1)
{
Nxt = *s.upb (v);
if (Nxt != INF) cover (C - Nxt, C - 1 - v, v);
else cover (0, C - 1 - v, v); // 更新对应的 f
split (root, v, x, y);
root = merge (merge (x, new_node (v, v1)), y); // 插入 pair(x,f(x))
}
void del (register int v)
{
split (root, v, x, z);
split (x, v - 1, x, y);
y = merge (t[y].ls, t[y].rs);
root = merge (merge (x, y), z);
it = s.lob (v); it--;
Pre = *it, Nxt = *s.upb (Pre);
if (~Pre) // 有前驱
{
if (Nxt != INF) cover (C - Nxt, C - 1 - Pre, Pre);
else cover (0, C - 1 - Pre, Pre);
update (Pre); // 删除 x 有可能影响 f(pre)
}
else if (Nxt != INF) cover (C - Nxt, C - 1, -INF); // 没有前驱,那么这部分的数将没有 f
if (Nxt != INF) update (Nxt); // 删除 x 有可能影响 f(nxt)
}
signed main ()
{
n = read (), C = read (); s.insert(-INF); s.insert (INF);
int lst = 0, op, x, tmp;
root = new_node (-1, 0);
while (n--)
{
op = read (), x = read () ^ lst;
x -= x / C * C;
if (op == 1)
{
it = s.upb (C - 1 - x); it--;
s.insert (x);
insert (x, *it);
}
else
{
s.erase (s.find(x));
del (x);
}
if (s.size () <= 3) *O++='E',*O++='E',*O++='\n', lst = 0;
else
{
mx1 = s.end(); --mx1;
tmp = *--mx1; tmp += *--mx1;
if (tmp >= C) tmp -= C;
print(lst = Max (t[root].mx, tmp));
*O++='\n';
}
}
fwrite(obuf,O-obuf,1,stdout); // 卡常快写,这部分可以直接掠过
return 0;
}
标签:return,rs,Ynoi2010,fast,trie,int,ls,now,define
From: https://www.cnblogs.com/violin-wyl/p/16884231.html