BZOJ3821 玄学
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);
}
}
}
