题目大意
有一个长度为 n 数列，有若干个事件，事件分为操作和询问两种，
一次操作是把数列[l...r] 区间中的每个元素x变成 ax + b mod p。
一次询问是询问 执行了 第l 次到第r次操作后第 k 个元素的值。
解题思路
标解是树套树，且平衡树一层需要写可持久化AVL来卡常。
松爷在考场上给出了一种编程复杂度更低的算法。
单独维护a,b两个系数，我们发现在这道题中的操作是支持结合律的，也就是说我们可以把一段操作后产生的效果提前预处理出来。
考虑用线段树维护把每一段区间操作执行后每一个元素的a和b的值。
等等。。每一个元素？那样的话岂不是要存下 线段树节点个数 * 序列中节点个数 个， 即 n^2 个点了吗？
但是这些点中很多个点的a和b值都是相同的， 很显然的一点是对于一个长度为L的区间， a,b值不同的段数是 O(L) 的。
所以说只要依次存下这L段的位置和a,b的值就可以了。 询问的时候需要先二分确定一下 k 这个数处于哪一段中。
具体实现的时候，因为包含r的区间一定只有在 r操作 出现后才会被询问到，所以说每一次插入的时候只要合并掉所有 R == p 的区间就可以了， 而每个区间只会被更新一次（即区间最右端点被插入的时候），所以复杂度得到保证。
加入操作复杂度为 O(logn)， 询问操作复杂度 O(log2n) 。
技巧总结
要挖掘操作自身的一些性质， 并且选用合适的数据结构进行维护。 比如说支持合并操作的就可以用线段树啦
代码
写得丑死了QAQ
听了题目描述一个longlong都没有用炸了好久QAQ
作死地用了vector速度慢得飞起QAQ
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAXN 200005
#define MAXT 2500005
#define pb push_back
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
vector <int> xx[MAXT], aa[MAXT], bb[MAXT];
int Q, tt, n, mod, num[MAXN], lastans, cntj, l, r, a, b, k;
long long A, B;
void jiemi(int &x){x ^= lastans;}
inline void update(int t){
int zuo = t + t, zz = , you = t + t + , yy = ;
int sz = xx[zuo].size()-, sy = xx[you].size()-;
while(){
xx[t].pb(max(xx[zuo][zz], xx[you][yy]));
aa[t].pb((long long)aa[zuo][zz]*aa[you][yy] % mod);
bb[t].pb(((long long)bb[zuo][zz]*aa[you][yy] % mod + bb[you][yy]) % mod);
if(zz == sz && yy == sy) break;
if((zz<sz) && ((yy == sy) || xx[zuo][zz+] < xx[you][yy+])) zz ++;
else if((yy<sy) && ((zz==sz) || xx[you][yy+] < xx[zuo][zz+])) yy ++;
else zz ++, yy ++;
}
}
void insert(int t, int l, int r, int L, int R, int p){
if(l == r){
if(L != ){xx[t].pb(); aa[t].pb(); bb[t].pb();}
xx[t].pb(L); aa[t].pb(a); bb[t].pb(b);
if(R != n){xx[t].pb(R+); aa[t].pb(); bb[t].pb();}
return;
}
int mid = l + r >> ;
if(mid >= p) insert(t + t, l, mid, L, R, p);
else insert(t + t + , mid + , r, L, R, p);
if(p == r) update(t);
}
inline int erfen(int t, int l, int r, int p){
while(l + < r){
int mid = l + r >> ;
if(xx[t][mid] <= p) l = mid;
else r = mid-;
}if(xx[t][r] <= p) return r; return l;
}
inline void ask(int t, int p){
int x = erfen(t, , xx[t].size()-, p);
A = (A*aa[t][x]) % mod; B = (B*aa[t][x]%mod+bb[t][x]) % mod;
}
void query(int t, int l, int r, int L, int R, int p){
if(l >= L && r <= R){ask(t, p); return;}
int mid = l + r >> ;
if(L <= mid)query(t + t, l, mid, L, R, p);
if(R >= mid+)query(t + t + , mid + , r, L, R, p);
}
int main(){
scanf("%d%d%d", &tt, &n, &mod);
for(int i = ; i <= n; i ++) num[i] = read();
scanf("%d", &Q);
for(int qq = ; qq <= Q; qq ++){
int cmd; cmd = read();
if(cmd == ){
l = read(); r = read(); a = read(); b = read();
if(tt % == ) jiemi(l), jiemi(r);
insert(, , Q, l, r, ++ cntj);
}else{
l = read(); r = read(); k = read();
if(tt % == ) jiemi(l), jiemi(r), jiemi(k);
A = ; B = ;
query(, , Q, l, r, k);
lastans = (A*num[k]%mod+B) % mod;
printf("%d\n", lastans);
}
}
// system("pause");
return ;
}