Infiltrator @ 2020-03-02 16:59:57
双旋WBLT90分T飞了
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const double aalpha = 0.6;
const double alpha = 0.29;
const int N = 4e7;
const int INF = 999999999;
int num, root, pool[N], poolsize, last, ans;
struct Node
{
int son[2], v, siz;
} tree[N];
template <class T>
void Read(T &x)
{
x = 0; int p = 0; char st = getchar();
while (st < '0' || st > '9') { p = (st == '-'); st = getchar(); }
while (st >= '0' && st <= '9') { x = (x << 1) + (x << 3) + (st ^ 48); st = getchar(); }
x = p ? -x : x;
return;
}
template <class T>
void Put(T x)
{
if (x < 0) { putchar('-'); x = -x; }
if (x > 9) Put(x / 10);
putchar(x % 10 + '0');
}
int Newnode(int x)
{
int k = poolsize ? pool[poolsize--] : ++num;
tree[k].siz = 1; tree[k].v = x; tree[k].son[0] = tree[k].son[1] = 0;
return k;
}
void Recycle(int k) { pool[++poolsize] = k; return; }
void Pushup(int k)
{
tree[k].siz = tree[tree[k].son[0]].siz + tree[tree[k].son[1]].siz;
tree[k].v = tree[tree[k].son[1]].v;
return;
}
void Rotate(int k, int d)
{
int temp = tree[k].son[d ^ 1];
tree[k].son[d ^ 1] = tree[k].son[d];
tree[k].son[d] = tree[tree[k].son[d ^ 1]].son[d];
tree[tree[k].son[d ^ 1]].son[d] = tree[tree[k].son[d ^ 1]].son[d ^ 1];
tree[tree[k].son[d ^ 1]].son[d ^ 1]=temp;
Pushup(tree[k].son[d ^ 1]);
Pushup(k);
}
void Maintain(int k)
{
int d;
if (tree[k].son[0])
{
if ((double)tree[tree[k].son[0]].siz < tree[k].siz * alpha) d = 1;
else if ((double)tree[tree[k].son[1]].siz < tree[k].siz * alpha) d = 0;
else return;
if ((double)tree[tree[tree[k].son[d]].son[d ^ 1]].siz >= tree[tree[k].son[d]].siz * aalpha) Rotate(tree[k].son[d], d ^ 1);
Rotate(k, d);
}
return;
}
void Insert(int &k,int x)
{
if (!k) { k = Newnode(x); return; }
if (tree[k].siz == 1)
{
tree[k].son[0] = Newnode(x); tree[k].son[1] = Newnode(tree[k].v);
if (x > tree[k].v) swap(tree[k].son[0], tree[k].son[1]);
}
else Insert(tree[k].son[x > tree[tree[k].son[0]].v], x);
Pushup(k); Maintain(k);
return;
}
void Delete(int &k,int x)
{
if (tree[k].siz == 1) { Recycle(k); k = 0; return; }
int d = x > tree[tree[k].son[0]].v;
if (tree[tree[k].son[d]].siz == 1)
{
if (tree[tree[k].son[d]].v == x)
{
Recycle(tree[k].son[d]);
Recycle(k);
k = tree[k].son[d ^ 1];
return;
}
}
else Delete(tree[k].son[d], x);
Pushup(k); Maintain(k);
return;
}
int Query_rank(int k,int x)
{
if (tree[k].siz == 1) return x > tree[k].v;
if (x > tree[tree[k].son[0]].v) return tree[tree[k].son[0]].siz + Query_rank(tree[k].son[1], x);
else return Query_rank(tree[k].son[0], x);
}
int Query_kth(int k,int x)
{
if (tree[k].siz == 1) return tree[k].v;
if (x > tree[tree[k].son[0]].siz) return Query_kth(tree[k].son[1], x - tree[tree[k].son[0]].siz);
else return Query_kth(tree[k].son[0], x);
}
int Pre(int k,int x)
{
if (tree[k].siz == 1) return tree[k].v < x ? tree[k].v : -INF;
if (tree[tree[k].son[0]].v < x) return max(tree[tree[k].son[0]].v, Pre(tree[k].son[1], x));
else return Pre(tree[k].son[0], x);
}
int Suf(int k,int x)
{
if (tree[k].siz == 1) return tree[k].v > x ? tree[k].v : INF;
if (tree[tree[k].son[0]].v > x)return Suf(tree[k].son[0], x);
else return Suf(tree[k].son[1], x);
}
void GGG(int k)
{
if(!k)return;
cout<<tree[k].v<<" "<<tree[k].siz<<endl;
cout<<"LEFT"<<endl;
GGG(tree[k].son[0]);
cout<<"RIGHT"<<endl;
GGG(tree[k].son[1]);
}
signed main()
{
int n, m, opt, x;
Read(n); Read(m);
Insert(root, INF);
for (int i = 1; i <= n; i++) Read(x), Insert(root, x);
for (int i = 1; i <= m; i++)
{
Read(opt); Read(x); x ^= last;
switch(opt)
{
case 1: Insert(root, x); break;
case 2: Delete(root, x); break;
case 3: ans ^= (last = Query_rank(root, x) + 1); break;
case 4: ans ^= (last = Query_kth(root, x)); break;
case 5: ans ^= (last = Pre(root, x)); break;
case 6: ans ^= (last = Suf(root, x)); break;
}
}
Put(ans);
return 0;
}by 7KByte @ 2020-03-02 17:01:10
WBLT啥啊
by George1123 @ 2020-03-02 17:03:31
@Tian_Xing 神天行
by George1123 @ 2020-03-02 17:03:40
°/。
by Infiltrator @ 2020-03-02 17:04:25
啊不对粘错代码了/jk
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const double aalpha = 0.6;
const double alpha = 0.29;
const int N = 4e7;
const int INF = 999999999;
int num, root, pool[N], poolsize, last, ans;
struct Node
{
int son[2], v, siz;
} tree[N];
template <class T>
void Read(T &x)
{
x = 0; int p = 0; char st = getchar();
while (st < '0' || st > '9') { p = (st == '-'); st = getchar(); }
while (st >= '0' && st <= '9') { x = (x << 1) + (x << 3) + (st ^ 48); st = getchar(); }
x = p ? -x : x;
return;
}
template <class T>
void Put(T x)
{
if (x < 0) { putchar('-'); x = -x; }
if (x > 9) Put(x / 10);
putchar(x % 10 + '0');
}
int Newnode(int x)
{
int k = poolsize ? pool[poolsize--] : ++num;
tree[k].siz = 1; tree[k].v = x; tree[k].son[0] = tree[k].son[1] = 0;
return k;
}
void Recycle(int k) { pool[++poolsize] = k; return; }
void Pushup(int k)
{
tree[k].siz = tree[tree[k].son[0]].siz + tree[tree[k].son[1]].siz;
tree[k].v = tree[tree[k].son[1]].v;
return;
}
void Rotate(int k, int d)
{
int temp = tree[k].son[d ^ 1];
tree[k].son[d ^ 1] = tree[k].son[d];
tree[k].son[d] = tree[tree[k].son[d ^ 1]].son[d];
tree[tree[k].son[d ^ 1]].son[d] = tree[tree[k].son[d ^ 1]].son[d ^ 1];
tree[tree[k].son[d ^ 1]].son[d ^ 1]=temp;
Pushup(tree[k].son[d ^ 1]);
Pushup(k);
}
void Maintain(int k)
{
int d;
if (tree[k].son[0])
{
if ((double)tree[tree[k].son[0]].siz < tree[k].siz * alpha) d = 1;
else if ((double)tree[tree[k].son[1]].siz < tree[k].siz * alpha) d = 0;
else return;
if ((double)tree[tree[tree[k].son[d]].son[d ^ 1]].siz >= tree[tree[k].son[d]].siz * aalpha) Rotate(tree[k].son[d], d ^ 1);
Rotate(k, d);
}
return;
}
void Insert(int &k,int x)
{
if (!k) { k = Newnode(x); return; }
if (tree[k].siz == 1)
{
tree[k].son[0] = Newnode(x); tree[k].son[1] = Newnode(tree[k].v);
if (x > tree[k].v) swap(tree[k].son[0], tree[k].son[1]);
}
else Insert(tree[k].son[x > tree[tree[k].son[0]].v], x);
Pushup(k); Maintain(k);
return;
}
void Delete(int &k,int x)
{
if (tree[k].siz == 1) { Recycle(k); k = 0; return; }
int d = x > tree[tree[k].son[0]].v;
if (tree[tree[k].son[d]].siz == 1)
{
if (tree[tree[k].son[d]].v == x)
{
Recycle(tree[k].son[d]);
Recycle(k);
k = tree[k].son[d ^ 1];
return;
}
}
else Delete(tree[k].son[d], x);
Pushup(k); Maintain(k);
return;
}
int Rank(int k,int x)
{
if (tree[k].siz == 1) return x > tree[k].v;
if (x > tree[tree[k].son[0]].v) return tree[tree[k].son[0]].siz + Rank(tree[k].son[1], x);
else return Rank(tree[k].son[0], x);
}
int Kth(int k,int x)
{
if (tree[k].siz == 1) return tree[k].v;
if (x > tree[tree[k].son[0]].siz) return Kth(tree[k].son[1], x - tree[tree[k].son[0]].siz);
else return Kth(tree[k].son[0], x);
}
int Pre(int k,int x)
{
if (tree[k].siz == 1) return tree[k].v < x ? tree[k].v : -INF;
if (tree[tree[k].son[0]].v < x) return max(tree[tree[k].son[0]].v, Pre(tree[k].son[1], x));
else return Pre(tree[k].son[0], x);
}
int Suf(int k,int x)
{
if (tree[k].siz == 1) return tree[k].v > x ? tree[k].v : INF;
if (tree[tree[k].son[0]].v > x)return Suf(tree[k].son[0], x);
else return Suf(tree[k].son[1], x);
}
void GGG(int k)
{
if(!k)return;
cout<<tree[k].v<<" "<<tree[k].siz<<endl;
cout<<"LEFT"<<endl;
GGG(tree[k].son[0]);
cout<<"RIGHT"<<endl;
GGG(tree[k].son[1]);
}
signed main()
{
int n, m, opt, x;
Read(n); Read(m);
for (int i = 1; i <= n; i++) Read(x), Insert(root, x);
for (int i = 1; i <= m; i++)
{
Read(opt); Read(x); x ^= last;
switch(opt)
{
case 1: Insert(root, x); break;
case 2: Delete(root, x); break;
case 3: ans ^= (last = Rank(root, x) + 1); break;
case 4: ans ^= (last = Kth(root, x)); break;
case 5: ans ^= (last = Kth(root, Rank(root, x))); break;
case 6: ans ^= (last = Kth(root, Rank(root, x + 1) + 1)); break;
}
}
Put(ans);
return 0;
}by xhQYm @ 2020-03-02 17:07:02
emmmm粘错代码可海星
by liqingyang @ 2020-03-02 17:08:33
%%%%
by liqingyang @ 2020-03-02 17:08:51
我都不知道WBLT是什么
by ZeyuJin_Yuki @ 2020-03-02 17:21:17
shift + 555555