laekov

Scoi2013多项式的运算

平衡树维护序列的老题。之前用SMT写过,不过在bzoj上就tle了。splay大法好。


#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


int _d_;

#define readInt(_x_) { \

int& _s_ = _x_; \

while (!isdigit(_d_ = getchar())); \

_s_ = 0; \

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar())); \

}

#define readStr(_s_) { \

char* _i_ = _s_; \

while (!islower(_d_ = getchar())); \

while ((*(_i_ ++) = _d_), islower(_d_ = getchar())); \

*(_i_) = 0; \

}

#define _l (long long int)


const int maxn = 300009;

const int mod = 20130426;


struct node {

int ls, rs, pt, sz;

int val, mul, add;

};

struct splay_tree {

node t[maxn];

int cr, tn;

void init() {

t[0]. sz = 0;

t[0]. val = 0;

tn = 0;

cr = 0;

}

inline void update(int p) {

t[p]. sz = t[t[p]. ls]. sz + t[t[p]. rs]. sz + 1;

}

inline void pushDown(int p) {

if (t[p]. ls) {

t[t[p]. ls]. val = (_l t[t[p]. ls]. val * t[p]. mul + t[p]. add) % mod;

t[t[p]. ls]. mul = (_l t[t[p]. ls]. mul * t[p]. mul) % mod;

t[t[p]. ls]. add = (_l t[t[p]. ls]. add * t[p]. mul + t[p]. add) % mod;

}

if (t[p]. rs) {

t[t[p]. rs]. val = (_l t[t[p]. rs]. val * t[p]. mul + t[p]. add) % mod;

t[t[p]. rs]. mul = (_l t[t[p]. rs]. mul * t[p]. mul) % mod;

t[t[p]. rs]. add = (_l t[t[p]. rs]. add * t[p]. mul + t[p]. add) % mod;

}

t[p]. mul = 1;

t[p]. add = 0;

}

inline void lRot(int q) {

int p = t[q]. pt, a = t[p]. pt;

if (t[q]. rs)

t[t[q]. rs]. pt = p;

t[p]. ls = t[q]. rs;

t[q]. rs = p;

t[p]. pt = q;

t[q]. pt = a;

if (a) {

if (p == t[a]. ls)

t[a]. ls = q;

else

t[a]. rs = q;

}

update(p);

update(q);

}

inline void rRot(int q) {

int p = t[q]. pt, a = t[p]. pt;

if (t[q]. ls)

t[t[q]. ls]. pt = p;

t[p]. rs = t[q]. ls;

t[q]. ls = p;

t[p]. pt = q;

t[q]. pt = a;

if (a) {

if (p == t[a]. ls)

t[a]. ls = q;

else

t[a]. rs = q;

}

update(p);

update(q);

}

void upath(int q) {

for (; q; q = t[q]. pt)

update(q);

}

void dpath(int q) {

static int stc[maxn];

int tst = 0;

for (int u = q; u; u = t[u]. pt)

stc[++ tst] = u;

for (; tst; -- tst) {

update(stc[tst]);

pushDown(stc[tst]);

}

}

void splay(int q) {

dpath(q);

while (t[q]. pt) {

int p = t[q]. pt, a = t[p]. pt;

if (!a || !t[a]. pt) {

if (q == t[p]. ls)

lRot(q);

else

rRot(q);

}

else {

if (p == t[a]. ls) {

if (q == t[p]. ls)

lRot(p), lRot(q);

else

rRot(q), lRot(q);

}

else {

if (q == t[p]. ls)

lRot(q), rRot(q);

else

rRot(p), rRot(q);

}

}

}

cr = q;

}

int kth(int k) {

int p = cr;

while (p)

if (t[t[p]. ls]. sz == k)

break;

else if (t[t[p]. ls]. sz > k)

p = t[p]. ls;

else

k -= t[t[p]. ls]. sz + 1, p = t[p]. rs;

return p;

}

int build(int l, int r) {

if (l > r)

return 0;

int p = ++ tn, mid = (l + r) >> 1;

t[p]. val = 0;

t[p]. add = 0;

t[p]. mul = 1;

t[p]. ls = build(l, mid - 1);

if (t[p]. ls)

t[t[p]. ls]. pt = p;

t[p]. rs = build(mid + 1, r);

if (t[p]. rs)

t[t[p]. rs]. pt = p;

update(p);

return p;

}

int getRange(int l, int r) {

if (!cr)

cr = build(0, r);

if (r >= t[cr]. sz) {

int x = kth(t[cr]. sz - 1);

int z = build(t[cr]. sz, r);

splay(x);

pushDown(x);

t[x]. rs = z;

t[z]. pt = x;

update(x);

}

if (!l && r == t[cr]. sz - 1)

return cr;

else if (!l) {

int x = kth(r + 1);

splay(x);

return t[x]. ls;

}

else if (r == t[cr]. sz - 1) {

int x = kth(l - 1);

splay(x);

return t[x]. rs;

}

else {

int x = kth(l - 1);

int y = kth(r + 1);

splay(x);

splay(y);

return t[x]. rs;

}

}

void add(int p, int v) {

dpath(p);

t[p]. val = (_l t[p]. val + v) % mod;

t[p]. add = (_l t[p]. add + v) % mod;

}

void mul(int p, int v) {

dpath(p);

t[p]. val = _l t[p]. val * v % mod;

t[p]. add = _l t[p]. add * v % mod;

t[p]. mul = _l t[p]. mul * v % mod;

}

int rmvKth(int k) {

int x = getRange(k, k);

if (t[cr]. sz == 1)

return cr = 0, t[x]. val;

dpath(x);

int ret = t[x]. val;

if (t[x]. pt) {

if (x == t[t[x]. pt]. ls)

t[t[x]. pt]. ls = 0; 

else

t[t[x]. pt]. rs = 0; 

upath(t[x]. pt);

}

return ret;

}

void ins(int k) {

int x = getRange(k, k);

while (t[x]. ls)

x = t[x]. ls;

dpath(x);

++ tn;

t[tn]. ls = 0;

t[tn]. rs = 0;

t[tn]. pt = x;

t[tn]. sz = 1;

t[tn]. val = 0;

t[tn]. mul = 1;

t[tn]. add = 0;

t[x]. ls = tn;

upath(tn);

splay(tn);

}

int dfsAns(int p, int& x, int x0) {

int ret = 0;

pushDown(p);

if (t[p]. ls)

ret = dfsAns(t[p]. ls, x, x0);

ret = (_l ret + _l x * t[p]. val) % mod;

x = _l x * x0 % mod;

if (t[p]. rs)

ret = (ret + dfsAns(t[p]. rs, x, x0)) % mod;

return ret;

}

int getAns(int x) {

int tmp = 1;

return dfsAns(cr, tmp, x);

}

};


int n;

splay_tree t;


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

t. init();

readInt(n);

while (n --) {

char opt[7];

int l, r, v;

readStr(opt);

if (opt[0] == 'm' && opt[3] == 0) {

readInt(l);

readInt(r);

readInt(v);

int x = t. getRange(l, r);

t. mul(x, v);

}

else if (opt[0] == 'a') {

readInt(l);

readInt(r);

readInt(v);

int x = t. getRange(l, r);

t. add(x, v);

}

else if (opt[3] == 'x') {

readInt(l);

readInt(r);

int v = t. rmvKth(r);

int x = t. getRange(r, r);

t. add(x, v);

t. ins(l);

}

else {

readInt(v);

printf("%d\n", t. getAns(v));

}

}

}


评论

© laekov | Powered by LOFTER