zhx+主席出的题,恐怖至极。


写此题需要极高的常数优化技巧+耐心。


本地跑到50s才在bzoj上压80s跑过。


其实思路就是拿线段树套AVL把询问的时间复杂度优化到O(logn)。


然后首先用treap会t爽+mle爽。


然后avl需要各种常数优化。


然后要在xxxxx地方优化。


加上zhx牌读入优化+块状内存+抄std的AVL+.....终于在81s过了。


orz比我快一倍的wangyisong神犇。


#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cstring>

#include <algorithm>


using namespace std;


const int BUF_SIZE = 300;

char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;

#define PTR_NEXT() \

{ \

buf_s ++; \

if (buf_s == buf_t) \

{ \

buf_s = buf; \

buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \

} \

}

#define readInt(_n_) \

{ \

while (*buf_s != '-' && !isdigit(*buf_s)) \

PTR_NEXT(); \

bool register _nega_ = false; \

if (*buf_s == '-') \

{ \

_nega_ = true; \

PTR_NEXT(); \

} \

int register _x_ = 0; \

while (isdigit(*buf_s)) \

{ \

_x_ = _x_ * 10 + *buf_s - '0'; \

PTR_NEXT(); \

} \

if (_nega_) \

_x_ = -_x_; \

(_n_) = (_x_); \

}


#define _l (long long int)


int mod, rsd;


struct oper {

int k, b;

inline oper() {

}

inline oper(int k0, int b0) {

k = k0, b = b0;

}

inline int ans(int x) {

return (_l x * k + b) % mod;

}

};

inline oper moper(const oper& x, const oper& y) {

return oper(_l x. k * y. k % mod, (_l x. b * y. k + y. b) % mod);

}


struct node {

int l, r, v, h;

oper d;

node *ls, *rs;

inline void set(int k, int b, int n) {

d. k = k;

d. b = b;

l = n;

r = n;

v = n;

h = 1;

ls = 0;

rs = 0;

}

inline void copy(node* u) {

v = u-> v;

d = u-> d;

h = u-> h;

}

inline void update() {

d = oper(1, 0);

h = 1;

if (ls) {

l = ls-> l;

d = moper(ls-> d, d);

h = ls-> h + 1;

}

else

l = v;

if (rs) {

r = rs-> r;

d = moper(d, rs-> d);

if (rs-> h + 1 > h)

h = rs-> h;

}

else

r = v;

}

};

struct seg {

int l, r;

node *d;

seg *ls, *rs;

};


const int maxn = 100009;

const int bsz = 888888;

const int balc = 5;


node *nodep;

int tnd = 0;

seg *sp, *rt;

int qua, n, m, lans, seq[maxn];


inline node* newNode() {

if (tnd)

return -- tnd, ++ nodep;

else

return nodep = new node[(tnd = bsz) + 1];

}


inline node* ptNew(node* p, node* q) {

node* r = newNode();

r-> d = moper(p-> d, q-> d);

r-> l = p-> l;

r-> r = q-> r;

r-> ls = p;

r-> rs = q;

r-> h = max(p-> h, q-> h) + 1;

return r;

}


#define hof(_p_) ((_p_)?(_p_->h):0)

#define lson(_p_) ((_p_)?(_p_->ls):0)

#define rson(_p_) ((_p_)?(_p_->rs):0)


inline node* ptMerge(node* p, node* q) {

if (!p)

return q;

else if (!q)

return p;

else if (p-> h <= q-> h + balc && q-> h <= p-> h + balc)

return ptNew(p, q);

else if (p-> h > q-> h) {

node* r = p-> rs;

if (hof(r) <= hof(p-> ls))

return ptNew(p-> ls, ptMerge(r, q));

else

return ptNew(ptNew(p-> ls, lson(r)), ptMerge(rson(r), q));

}

else {

node* r = q-> ls;

if (hof(r) <= hof(q-> rs))

return ptNew(ptMerge(p, r), q-> rs);

else

return ptNew(ptMerge(p, lson(r)), ptNew(rson(r), q-> rs));

}

}


int ql, qr;

inline oper ptQry(node* p) {

if (!p)

return oper(1, 0);

else if (ql > p-> r || qr < p-> l)

return oper(1, 0);

else if (ql <= p-> l && qr >= p-> r)

return p-> d;

else {

oper s(1, 0);

if (p-> ls && ql <= p-> ls-> r)

s = ptQry(p-> ls);

if (p-> rs && qr >= p-> rs-> l)

s = moper(s, ptQry(p-> rs));

return s;

}

}


#define mid(p) ((p->l+p->r)>>1)


inline seg* sgtBuild(int l, int r) {

seg* p = sp ++;

p-> l = l;

p-> r = r;

p-> d = 0;

if (l + 1 < r) {

p-> ls = sgtBuild(l, mid(p));

p-> rs = sgtBuild(mid(p), r);

}

return p;

}


inline void pushDown(seg* p) {

p-> ls-> d = ptMerge(p-> ls-> d, p-> d);

p-> rs-> d = ptMerge(p-> rs-> d, p-> d);

p-> d = 0;

}


inline void sgtChg(seg* p, int l, int r, node* x) {

if (p-> l == l && p-> r == r) {

p-> d = ptMerge(p-> d, x);

}

else {

if (p-> d)

pushDown(p);

if (r <= mid(p))

sgtChg(p-> ls, l, r, x);

else if (l >= mid(p))

sgtChg(p-> rs, l, r, x);

else {

sgtChg(p-> ls, l, mid(p), x);

sgtChg(p-> rs, mid(p), r, x);

}

}

}


oper sgtQry(seg* p, int p0) {

oper s(1, 0);

while (p-> l + 1 < p-> r) {

s = moper(ptQry(p-> d), s);

if (p0 < mid(p))

p = p-> ls;

else

p = p-> rs;

}

return moper(ptQry(p-> d), s);

}


inline void writeInt(int x) {

static char a[13];

char* i;

for (i = a; x; x /= 10, ++ i)

*i = x % 10 + 48;

if (i == a)

puts("0");

else {

for (-- i; i >= a; -- i)

putchar(*i);

putchar(10);

}

}


int main() {

#ifndef ONLINE_JUDGE

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

#endif


readInt(qua);

qua &= 1;

readInt(n);

readInt(mod);

for (int i = 1; i <= n; ++ i)

readInt(seq[i]);

readInt(m);

lans = 0;

sp = new seg[n * 3];

rt = sgtBuild(1, n + 1);

for (int i = 1, j = 0; i <= m; ++ i) {

int opt, a, b, l, r;

readInt(opt);

readInt(l);

readInt(r);

if (qua) {

l ^= lans;

r ^= lans;

}

if (opt == 1) {

readInt(a);

readInt(b);

node* x = newNode();

x-> set(a, b, ++ j);

sgtChg(rt, l, r + 1, x);

}

else {

readInt(a);

if (qua)

a ^= lans;

ql = l;

qr = r;

lans = sgtQry(rt, a). ans(seq[a]);

//writeInt(lans);

printf("%d\n", lans);

}

}

}