Fork me on GitHub

Uoj#46.【清华集训2014】玄学

Uoj#46. 【清华集训2014】玄学

题意:

  • 给定$n$个数,$m$次操作有两种:
    • 增加一个操作,将区间$[l,r]$中的数$x$变为$(ax+b) \bmod m$。
    • 执行编号区间$[l,r]$内的操作,询问第$k$个数的值。
  • $n\le 100000,m\le 600000$。

题解:

  • 考虑用线段树维护操作区间。
  • 考虑到$len$个操作至多可以将原数列分为$O(len)$段,所以如果采用归并,节点信息的合并就是$O(size)$ 的。
  • 对于每个线段树节点,我们只在它完全被加入完毕后进行节点信息的合并(操作数达到其右端点),这样每个节点最多被合并一次,合并复杂度就是$O(m\log m)$。
  • 询问的时候对于每个定位到的线段树节点二分查找到所在位置,因为每个节点的断点数是$O(size)$的,所以每次询问的总复杂度还是$O(\log n)$的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
#define gc getchar()
#define N 600009
#define M 10000009
#define ll long long
#define root 1,1,q
#define mid (l+r>>1)
#define lc cur<<1
#define rc lc|1
#define lson lc,l,mid
#define rson rc,mid+1,r
using namespace std;
int is_inline,t,cnt,q,n,mod,Ans,a[N],beg[N<<2],ed[N<<2];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return x*s;
}
struct node
{
int k,a,b;
node(int k=0,int a=0,int b=0):k(k),a(a),b(b){}
}p[M];
void get_Ans(int l,int r,int val)
{
int ret=0;
while (l<=r)
if (p[mid].k>=val) ret=mid,r=mid-1;
else l=mid+1;
Ans=((ll)Ans*p[ret].a%mod+p[ret].b)%mod;
}
void qry(int cur,int l,int r,int L,int R,int val)
{
if (L<=l&&R>=r)
{
get_Ans(beg[cur],ed[cur],val);
return;
}
if (L<=mid) qry(lson,L,R,val);
if (R>mid) qry(rson,L,R,val);
}
void ins(int cur,int l,int r,int x,int y,int X,int Y)
{
if (l==r)
{
beg[cur]=cnt+1;
if (x>1) p[++cnt]=node(x-1,1,0);
p[++cnt]=node(y,X,Y);
if (y<n) p[++cnt]=node(n,1,0);
ed[cur]=cnt;
return;
}
if (t<=mid) ins(lson,x,y,X,Y);
else ins(rson,x,y,X,Y);
if (t<r) return;
beg[cur]=cnt+1;
int i=beg[lc],j=ed[lc],u=beg[rc],v=ed[rc];
while (i<=j&&u<=v)
{
p[++cnt]=node(min(p[i].k,p[u].k),(ll)p[i].a*p[u].a%mod,((ll)p[u].a*p[i].b%mod+p[u].b)%mod);
if (p[i].k==p[cnt].k) i++;
if (p[u].k==p[cnt].k) u++;
}
while (i<=j) p[++cnt]=p[i];
while (u<=v) p[++cnt]=p[u];
ed[cur]=cnt;
}
int main()
{
is_inline=read()&1,n=read(),mod=read();
for (int i=1;i<=n;i++) a[i]=read();
q=read();
for (int i=1;i<=q;i++)
{
int op=read();
if (op==1)
{
int x=read(),y=read(),X=read(),Y=read();
if (is_inline) x^=Ans,y^=Ans;
t++;
ins(root,x,y,X,Y);
}
else
{
int x=read(),y=read(),pos=read();
if (is_inline) x^=Ans,y^=Ans,pos^=Ans;
Ans=a[pos]%mod;
qry(root,x,y,pos);
printf("%d\n",Ans);
}
}
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#46.【清华集训2014】玄学

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj46/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。