题目大意
给出一个 (n) 个点的序列，有 (m) 次操作，每次操作为以下两种：
-
将 (l o r) 的点都变为 (ax+b)
-
查询在 (l o r) 修改操作情况下序列第 (k) 个数是多少。
强制在线，(nle 10^5,mle 6 imes 10^5)
思路
二进制分组好啊！！！
跟普通的二进制分组不太一样，这道题查询的一段区间的操作总和，所以我们自然而言地想到了线段树，而且线段树有一个好处，就是说每一段恰好就是 (2^x) 这种形态的，于是查询的时候直接跟在线段树查询一样地操作即可。
考虑修改操作，我们发现其实每次修改，都会有一段一段的区间是相同的变化规则，我们可以根据这个将两个操作进行合并。
考虑时间复杂度，你每次增加的时候最多增加 (3) 段，于是总段数就是 (nlog^2 n)，总时间复杂度也是 (Theta(nlog^2 n))（假设 (n,m) 同阶）
( exttt{Code})
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define MAXM 600005
#define MAXN 100005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,k,q,cnt,ans,kase,val[MAXN],lef[MAXM << 2],rig[MAXM << 2];
struct node{
int l,r,a,b;//表示l->r这段区间都变为ax+b
node(){}
node (int _l,int _r,int _a,int _b){l = _l,r = _r,a = _a,b = _b;}
}p[MAXM * 200];
void Pushup (int x){
lef[x] = cnt + 1;
for (Int i = lef[x << 1],j = lef[x << 1 | 1],las = 1;i <= rig[x << 1] || j <= rig[x << 1 | 1];)
if (p[i].r <= p[j].r){
p[++ cnt] = node (las,p[i].r,1ll * p[i].a * p[j].a % m,(1ll * p[i].b * p[j].a % m + p[j].b) % m);
las = p[i].r + 1;
if (p[i].r == p[j].r) ++ i,++ j;
else ++ i;
}
else{
p[++ cnt] = node (las,p[j].r,1ll * p[i].a * p[j].a % m,(1ll * p[i].b * p[j].a % m + p[j].b) % m);
las = p[j].r + 1,++ j;
}
rig[x] = cnt;
}
void find (int x,int t,int &s){//在x维护的段内
int l = lef[x],r = rig[x];
while (l < r){
int mid = (l + r) >> 1;
if (t <= p[mid].r) r = mid;
else l = mid + 1;
}
s = (1ll * s * p[l].a % m + p[l].b) % m;
}
void Modify (int x,int l,int r,int pos,node &t){
if (l == r){
lef[x] = cnt + 1;
if (t.l > 1) p[++ cnt] = node (1,t.l - 1,1,0);
p[++ cnt] = t;
if (t.r < n) p[++ cnt] = node (t.r + 1,n,1,0);
rig[x] = cnt;
return ;
}
int mid = (l + r) >> 1;
if (pos <= mid) Modify (x << 1,l,mid,pos,t);
else Modify (x << 1 | 1,mid + 1,r,pos,t);
if (pos == r) Pushup (x);
}
void Query (int x,int l,int r,int ql,int qr){
if (ql <= l && r <= qr) return find (x,k,ans);
int mid = (l + r) >> 1;
if (ql <= mid) Query (x << 1,l,mid,ql,qr);
if (qr > mid) Query (x << 1 | 1,mid + 1,r,ql,qr);
}
signed main(){
read (kase,n,m);
for (Int i = 1;i <= n;++ i) read (val[i]);
read (q);int tot = 0;
for (Int i = 1;i <= q;++ i){
int opt,l,r;read (opt,l,r);
if (kase & 1) l ^= ans,r ^= ans;
if (opt == 1){
int ta,tb;read (ta,tb);
node now = node (l,r,ta,tb);
Modify (1,1,q,++ tot,now);
}
else{
read (k);
if (kase & 1) k ^= ans;
ans = val[k],Query (1,1,q,l,r);
write (ans),putchar ('
');
}
}
return 0;
}