題目描述 過長……不想發圖也不想發文字，所以就發鏈接吧…… [沒有人的算術][1] 題解 $orz$神題一枚 我們考慮如果插入的數不是數對，而是普通的數，這就是一道傻題了——直接線段樹一頓亂上就可以了。 於是我們現在只需要解決一個問題——維護這些數的大小關係。 由於這些數具有有序性，我們可以將這些數 ...
題目描述
過長……不想發圖也不想發文字，所以就發鏈接吧……
沒有人的算術
題解
\(orz\)神題一枚
我們考慮如果插入的數不是數對，而是普通的數，這就是一道傻題了——直接線段樹一頓亂上就可以了。
於是我們現在只需要解決一個問題——維護這些數的大小關係。
由於這些數具有有序性，我們可以將這些數的值重記為一個數，這樣就可以無腦地比較了。並且，由於這些值的大小可能會隨著插入而更改，所以要用一棵平衡樹來維護。
那麼問題來了，這個數取什麼值比較好呢？
首先當然可以是排名，不過如果使用排名，每次訪問值的時候都要重新在平衡樹中查一次，複雜度肯定是\(O(nlog^2n)\)的，基本不現實。
換一個角度可以發現，我們只需要知道大小關係，不需要排名，於是我們可以用實數維護一個數的大小，雖然相鄰的數差值大小不同，只要相對大小是正確的就不必擔心了……
那麼我們可以這樣看，在平衡樹中每個節點維護一個區間\((l,r)\)，表示這棵子樹中所有數值都在\((l,r)\)之中，而這棵子樹的根的值為\(mid=\frac{(l+r)}{2}\)遞歸左右子樹的時候，將區間分成\((l,mid)\)和\((mid,r)\)，完全滿足二叉搜索樹的性質，並且可以隨時在任何位置新增一個數而不影響已有的數的數值。
那麼問題就得到瞭解決，我們用一棵平衡樹維護出現過的所有數對，節點上保存這個數對的兩個父親和\((l,r)\)，並用\(mid=\frac{(l+r)}{2}\)表示這個節點的數值，然後無腦做插入和詢問即可。
但是我們忽略了一個問題，我們應該使用什麼樣的平衡樹？發現那些基於旋轉的平衡樹在旋轉後都會出現一個致命的問題，\((l,r)\)無法維護！因為一次旋轉會使得它以及它的子樹全部的\((l,r)\)都被改變，複雜度難以承受。於是我們想到了替罪羊樹，基於重構的它反正都要全部拍扁了重來，重新為區間賦值不就可以在重構時順便一起做了嗎？
於是，這道題就這麼被切掉了……
（內心：哪有說的這麼簡單）
總結：
替罪羊樹的維護方式與\(AVL\)、\(SBT\)、\(Splay\)都不一樣，後幾種演算法都是通過旋轉維護平衡，然而替罪羊樹卻是用重構維護平衡，重構的時候可以重新計算值，不需要通過原來的值進行改變。所以替罪羊樹可以維護的信息更加靈活，並且拍扁重建很歡樂常數小。於是替罪羊樹非常適合套其他的數據結構……樹套樹時也要想一想能不能用替罪羊樹……
吐槽：植樹節到了我們一起來歡樂種樹寫替罪羊樹模板吧！
\(Code:\)
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 100005
#define M 800005
#define eps 1e-10
#define inf 1e20
#define equal(a, b) (fabs((a) - (b)) < eps)
#define val(a) (a == -1 ? -inf :(ls[a] + rs[a])/ 2)
#define lim 0.77
char opt[10];
int n, m;
void Insert(int q, int l, int r, int k, int a);
int getint()
{
int p=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')p=p*10+c-'0',c=getchar();
return p;
}
struct SCT
{
int root, cnt, sz[M];
int num, arr[M];
int lc[M], rc[M];
int lf[M], rf[M];
double ls[M], rs[M];
bool Equal(int u, int l, int r)
{
return equal(val(lf[u]), val(l)) && equal(val(rf[u]), val(r));
}
bool Less(int u, int l, int r)
{
return equal(val(lf[u]), val(l)) ? val(rf[u]) < val(r) : val(lf[u]) < val(l);
}
void Pushup(int q)
{
sz[q] = sz[lc[q]] + sz[rc[q]] + 1;
}
void Getarray(int q)
{
if (lc[q])
Getarray(lc[q]);
arr[++num] = q;
if (rc[q])
Getarray(rc[q]);
}
void Rebuild(int &q, int l, int r, double L, double R)
{
if (l > r)
{
q = 0;
return;
}
int mid = (l + r) >> 1;
double Mid = (L + R) / 2;
q = arr[mid];
ls[q] = L;
rs[q] = R;
Rebuild(lc[q], l, mid - 1, L, Mid);
Rebuild(rc[q], mid + 1, r, Mid, R);
Pushup(q);
}
void Maintain(int &q)
{
num = 0;
Getarray(q);
Rebuild(q, 1, num, ls[q], rs[q]);
}
void Add(int &q, int l, int r, double L, double R, int k)
{
if (!q)
{
q = ++cnt;
lf[q] = l, rf[q] = r;
ls[q] = L, rs[q] = R;
sz[q] = 1;
Insert(1, 1, n, k, cnt);
return;
}
if (Equal(q, l, r))
{
Insert(1, 1, n, k, q);
return;
}
if (Less(q, l, r))
Add(rc[q], l, r, (L + R) / 2, R, k);
else
Add(lc[q], l, r, L, (L + R) / 2, k);
Pushup(q);
}
void Check(int &q, int l, int r)
{
if (sz[q] * lim < sz[lc[q]] || sz[q] * lim < sz[rc[q]])
{
Maintain(q);
return;
}
if (Equal(q, l, r))
return;
if (Less(q, l, r))
Check(rc[q], l, r);
else
Check(lc[q], l, r);
}
}T;
struct data
{
int plc, num;
data(){}
data(int a, int b){plc = a, num = b;}
double Val(){return (T.ls[num] + T.rs[num])/ 2;}
data operator + (data b)
{
if (num == 1 && b.num == 1)
return plc < b.plc ? *this : b;
if (num == 1)
return b;
if (b.num == 1)
return *this;
if (equal(Val(), b.Val()))
return plc < b.plc ? *this : b;
if (Val() > b.Val())
return *this;
return b;
}
};
struct SGT
{
data a[N << 2];
}S;
void Insert(int q, int l, int r, int k, int a)
{
if (l == k && r == k)
{
S.a[q] = data(k, a);
return;
}
int mid = (l + r) >> 1;
if (k <= mid)
Insert(q << 1, l, mid, k, a);
else
Insert(q << 1 | 1, mid + 1, r, k, a);
S.a[q] = S.a[q << 1] + S.a[q << 1 | 1];
}
data Query(int q, int l, int r, int L, int R)
{
if (l == L && r == R)
return S.a[q];
int mid = (l + r) >> 1;
if (R <= mid)
return Query(q << 1, l, mid, L, R);
if (L > mid)
return Query(q << 1 | 1, mid + 1, r, L, R);
return Query(q << 1, l, mid, L, mid) + Query(q << 1 | 1, mid + 1, r, mid + 1, R);
}
int main()
{
n = getint(), m = getint();
T.root = T.cnt = 1;
T.lf[1] = T.rf[1] = -1;
T.ls[1] = 0, T.rs[1] = 1;
for (int i = 1; i <= n; i++)
Insert(1, 1, n, i, 1);
for (int i = 1; i <= m; i++)
{
scanf("%s", opt);
if (opt[0] == 'Q')
{
int l = getint(), r = getint();
printf("%d\n", Query(1, 1, n, l, r).plc);
}
else
{
int l = getint(), r = getint(), k = getint();
l = Query(1, 1, n, l, l).num;
r = Query(1, 1, n, r, r).num;
T.Add(T.root, l, r, 0, 1, k);
T.Check(T.root, l, r);
}
}
}
