hdu6667
###name Roundgod and Milk Tea
###decription Roundgod is a famous milk tea lover at Nanjing University second to none. This year, he plans to conduct a milk tea festival. There will be n classes participating in this festival, where the ith class has ai students and will make bi cups of milk tea.
Roundgod wants more students to savor milk tea, so he stipulates that every student can taste at most one cup of milk tea. Moreover, a student can't drink a cup of milk tea made by his class. The problem is, what is the maximum number of students who can drink milk tea?
###input The first line of input consists of a single integer T (1≤T≤25), denoting the number of test cases.
Each test case starts with a line of a single integer n \((1≤n≤10^6)\), the number of classes. For the next n lines, each containing two integers a,b (0≤a,b≤109), denoting the number of students of the class and the number of cups of milk tea made by this class, respectively.
It is guaranteed that the sum of n over all test cases does not exceed \(6×10^6\).
###output For each test case, print the answer as a single integer in one line.
###sample input 1 2 3 4 2 1
###sample output 3
###toturial 霍尔定理
###code 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
typedef long long ll;
const int maxn=1e6+6;
ll a[maxn],b[maxn];
int main(){
ll t; scanf("%lld",&t);
while(t--){
ll n; scanf("%lld",&n);
ll sa=0,sb=0,mx=0;// 空集
rep(i,1,n) scanf("%lld%lld",a+i,b+i),sa+=a[i],sb+=b[i];
rep(i,1,n) mx=max(mx,a[i]-(sb-b[i]));// 子集中一个元素
printf("%lld\n",sa-max(mx,sa-sb));// 子集中大于一个元素
}
}
hdu5634
name
Rikka with Phi
decription
Rikka and Yuta are interested in Phi function (which is known as Euler's totient function). Yuta gives Rikka an array A[1..n] of positive integers, then Yuta makes m queries. There are three types of queries:
1lr Change A[i] into φ(A[i]), for all i∈[l,r].
2lrx Change A[i] into x, for all i∈[l,r].
3lr Sum up A[i], for all i∈[l,r]. Help Rikka by computing the results of queries of type 3.
input
The first line contains a number T(T≤100) ——The number of the testcases. And there are no more than 2 testcases with \(n>10^5\) For each testcase, the first line contains two numbers n,m(\(n≤3×10^5,m≤3×10^5\))。 The second line contains n numbers A[i] Each of the next m lines contains the description of the query. It is guaranteed that \(1≤A[i]≤10^7\) At any moment.
output
For each query of type 3, print one number which represents the answer.
sample input
1 10 10 56 90 33 70 91 69 41 22 77 45 1 3 9 1 1 10 3 3 8 2 5 6 74 1 1 8 3 1 9 1 2 10 1 4 9 2 8 8 69 3 3 9
sample output
80 122 86
toturial
phi函数求不了几次就会变成1,区间修改只会让区间值变化为相同，两个修改都逐渐让区间值变成相同。所以可以用线段树维护一个区间最大值，一个区间最小值，当区间最大值等于区间最小值的时候，我们可以把求phi操作对整个区间一起做了。 第二点，这个问题如果用splay将达到更高的效率，区间赋值的时候，我们直接在splay上删除原区间，用一个节点代替，求phi同理，跑起来飞快
code-线段树
1 |
|
code-splay
1 |
|
splay
1 | //初始化时要初始化tot和stk[0] |
线段树
1 |
|
hdu6647
###name Bracket Sequences on Tree
###decription Cuber QQ knows about DFS on an undirected tree, he's sure that you are familiar with it too. In case you are not, Cuber QQ is delighted to share with you a snippet of pseudo code:
function dfs(int cur, int parent): print('(') for all nxt that cur is adjacent to: dfs(nxt, cur) print(')')
You might notice that Cuber QQ print a "(" when entering a node, and a ")" when leaving a node. So when he finishes this DFS, in his console, he will see a bracket sequence of length 2n, where n is the number of vertices in the tree.
Obviously, if the tree is undirected and the nodes are unlabelled (meaning that all the nodes are treated equally), you can get a lot of different bracket sequences when you do the DFS. There are two reasons accounting for this. Firstly, when you are at cur, you can follow any permutation of the nodes that cur is adjacent to when you visit nxt. Secondly, the entrance to the tree, that is the root, is undeterministic when you start your DFS.
So Cuber QQ couldn't help wondering how many distinct bracket sequences he can get possibly. As the answer can be very large, output it modulo 998 244 353.
###input The first line of the input consists of one integer t \((1≤t≤10^5)\), which is the number of the test cases.
For each test case, the tree is given in a standard format, which you might be very familiar with: first line n \((1≤n≤10^5)\), the size of tree; then n−1 lines, each consisting of two space-separated integers u, v (1≤u,v≤n, u≠v), denoting an edge.
The sum of n from all test cases does not exceed \(3.2×10^6\).
###output For each test case, output the answer in one line.
###sample input 3 4 1 3 2 3 4 3 5 1 2 2 3 3 4 4 5 5 1 2 2 3 3 4 3 5
###sample output 2 4 8
###toturial 其实很简单，就一个树hash然后树dp就秒掉了，但是由于之前学某博客的树hash，结果冲突掉了，最后看了杨弋的论文才懂了怎么一回事
###code 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
using namespace std;
typedef pair<int,int> pii;
const int maxn=2e5+5;
// tree 节点0不准使用
int head[maxn];// point
int to[maxn*2],nex[maxn*2],tot;// edge
inline void _addedge(int u,int v){to[++tot]=v,nex[tot]=head[u],head[u]=tot;}
inline void addedge(int u,int v){_addedge(u,v),_addedge(v,u);}
void deltree(int rt,int father){// deltree() and also don't forget tot
for(int i=head[rt];i;i=nex[i]) if(to[i]!=father) deltree(to[i],rt);
head[rt]=0;
}
// struct tree{int rt,n;}
//tree hash
int pw[maxn*2]={1},hshmod;//pw要两倍
int *hsh,siz[maxn]; //point
int *ehsh; //edge
void dfs(int u,int father){
siz[u]=1;
for(int i=head[u];i;i=nex[i]){
if(to[i]==father)continue;
dfs(to[i],u), siz[u]+=siz[to[i]];
}
}
void dfs1(int u,int father){// solve every edge from father->u
for(int i=head[u];i;i=nex[i]){
if(to[i]==father) continue;
dfs1(to[i],u);
vector<pii>buf;
for(int j=head[to[i]];j;j=nex[j]){
if(to[j]==u) continue;
buf.emplace_back(ehsh[j],2*siz[to[j]]);
}
sort(buf.begin(),buf.end());
ehsh[i]=1;// 左边放1
for(pii x:buf) ehsh[i]=(1ll*ehsh[i]*pw[x.second]+x.first)%hshmod;
ehsh[i]=(1ll*ehsh[i]*pw[1]+2)%hshmod;// 右边放2
}
}
void dfs2(int u,int father,int rt){
vector<pii>buf;
for(int i=head[u];i;i=nex[i]) {
if(to[i]==father) buf.emplace_back(ehsh[i],2*(siz[rt]-siz[u]));
else buf.emplace_back(ehsh[i],2*siz[to[i]]);
}
sort(buf.begin(),buf.end());
hsh[u]=1;// 左边放1
for(pii x:buf) hsh[u]=(1ll*hsh[u]*pw[x.second]+x.first)%hshmod;
hsh[u]=(1ll*hsh[u]*pw[1]+2)%hshmod;// 右边放2
vector<pii>pre(buf),suf(buf);// 对后面进行处理
int sz=suf.size();
for(int i=1,j=sz-2;i<sz;i++,j--){
pre[i].first=(1ll*pre[i-1].first*pw[pre[i].second]+pre[i].first)%hshmod;// merge i-1 and i
suf[j].first=(1ll*suf[j].first*pw[suf[j+1].second]+suf[j+1].first)%hshmod;// merge j and j+1
pre[i].second+=pre[i-1].second;
suf[j].second+=suf[j+1].second;
}
for(int i=head[u];i;i=nex[i]){
if(father==to[i]) continue;
ehsh[i^1]=1;//左边放1
int idx=lower_bound(buf.begin(),buf.end(),pii(ehsh[i],2*siz[to[i]]))-buf.begin();
if(idx-1>=0) ehsh[i^1]=(1ll*ehsh[i^1]*pw[pre[idx-1].second]+pre[idx-1].first)%hshmod;// 前缀
if(idx+1<sz) ehsh[i^1]=(1ll*ehsh[i^1]*pw[suf[idx+1].second]+suf[idx+1].first)%hshmod;// 后缀
ehsh[i^1]=(1ll*ehsh[i^1]*pw[1]+2)%hshmod;//右边放2
dfs2(to[i],u,rt);
}
}
void treehash(int u,int*hsh_,int*ehsh_,int base,int hshmod_){//hash all tree of tree u
hsh=hsh_,ehsh=ehsh_,hshmod=hshmod_;
dfs(u,0); for(int i=1;i<=siz[u]*2;i++) pw[i]=1ll*pw[i-1]*base%hshmod;
dfs1(u,0),dfs2(u,0,u);
}
////// end
const int mod=998244353;
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int fac[maxn]={1},rev[maxn]={1};
void ini(){
for(int i=1;i<maxn;i++) fac[i]=1ll*fac[i-1]*i%mod;
rev[maxn-1]=qpow(fac[maxn-1],mod-2);
for(int i=maxn-2;i>=0;i--) rev[i]=1ll*rev[i+1]*(i+1)%mod;
}
int myhsh[4][maxn],ans[maxn]; // point
int myehsh[4][maxn*2],eans[maxn*2]; // edge
void dfs3(int u,int father){// solve edge from father->u
for(int i=head[u];i;i=nex[i]){
if(to[i]==father) continue;
dfs3(to[i],u);
map<__int64,pii>mp;
int son=0;
for(int j=head[to[i]];j;j=nex[j]){
if(to[j]==u) continue;
__int64 key=get64(myehsh[0][j],myehsh[1][j]);
if(mp.find(key)!=mp.end()) mp[key].first++;
else mp[key]=pii(1,eans[j]);// 数量+方案
son++;
}
eans[i]=fac[son];//全排列
for(auto it:mp){
eans[i]=1ll*eans[i]*rev[it.second.first]%mod;//去全排
eans[i]=1ll*eans[i]*qpow(it.second.second,it.second.first)%mod;//自排
}
}
}
void dfs4(int u,int father){
map<__int64,pii>mp;
int son=0;
for(int i=head[u];i;i=nex[i]) {
__int64 key=get64(myehsh[0][i],myehsh[1][i]);
if(mp.find(key)!=mp.end()) mp[key].first++;
else mp[key]=pii(1,eans[i]);// 数量+方案
son++;
}
ans[u]=fac[son];
for(auto it:mp){
ans[u]=1ll*ans[u]*rev[it.second.first]%mod;//去全排
ans[u]=1ll*ans[u]*qpow(it.second.second,it.second.first)%mod;//自排
}
for(int i=head[u];i;i=nex[i]){
if(to[i]==father) continue;
__int64 key=get64(myehsh[0][i],myehsh[1][i]);
int a=mp[key].first, x=eans[i];// a^x
eans[i^1]=1ll*ans[u]*a%mod*qpow(1ll*x*son%mod,mod-2)%mod;
dfs4(to[i],u);
}
}
int main(){
ini();
int times;scanf("%d",×);
while(times--){
tot=1;
int n;scanf("%d",&n);
for(int i=0;i<n-1;i++){
int u,v;scanf("%d%d",&u,&v);
addedge(u,v);
}
int b[]={3,5},p[]={1000000009,1000000009};
for(int i=0;i<2;i++) treehash(1,myhsh[i],myehsh[i],b[i],p[i]);
dfs3(1,0),dfs4(1,0);
map<__int64,int>mp;
long long res=0;
for(int i=1;i<=n;i++) {
__int64 key=get64(myhsh[0][i],myhsh[1][i]);
if(mp[key]==0) res+=ans[i];// ans<1e14
mp[key]=1;
}
printf("%d\n",int(res%mod));
deltree(1,0),tot=1;
}
}
bzoj4999
name
This Problem Is Too Simple！
description
给您一颗树，每个节点有个初始值。 现在支持以下两种操作： 1. C i x(0<=x<2^31) 表示将i节点的值改为x。 2. Q i j x(0<=x<2^31) 表示询问i节点到j节点的路径上有多少个值为x的节点。
input
第一行有两个整数N,Q（1 ≤N≤ 100,000；1 ≤Q≤ 200,000），分别表示节点个数和操作个数。 下面一行N个整数，表示初始时每个节点的初始值。 接下来N-1行，每行两个整数x,y，表示x节点与y节点之间有边直接相连（描述一颗树）。 接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出。
output
对于每个Q输出单独一行表示所求的答案。
sample input
5 6 10 20 30 40 50 1 2 1 3 3 4 3 5 Q 2 3 40 C 1 40 Q 2 3 40 Q 4 5 30 C 3 10 Q 4 5 30
sample output
0 1 1 0
toturial
树剖后直接对每一个数值都维护一颗权制线段树，动态开点即可
code
1 |
|
hdu4578
###name Transformation
###description Yuanfang is puzzled with the question below: There are n integers, \(a_1, a_2, …, a_n\). The initial values of them are 0. There are four kinds of operations. Operation 1: Add c to each number between ax and ay inclusive. In other words, do transformation \(a_k=a_k+c\), k = x,x+1,…,y. Operation 2: Multiply c to each number between ax and ay inclusive. In other words, do transformation \(a_k=a_k×c\), k = x,x+1,…,y. Operation 3: Change the numbers between ax and ay to c, inclusive. In other words, do transformation \(a_k=c\), k = x,x+1,…,y. Operation 4: Get the sum of p power among the numbers between ax and ay inclusive. In other words, get the result of \(a_x^p+a_{x+1}^p+…+a_y^p\). Yuanfang has no idea of how to do it. So he wants to ask you to help him.
###input There are no more than 10 test cases. For each case, the first line contains two numbers n and m, meaning that there are n integers and m operations. 1 <= n, m <= 100,000. Each the following m lines contains an operation. Operation 1 to 3 is in this format: "1 x y c" or "2 x y c" or "3 x y c". Operation 4 is in this format: "4 x y p". (1 <= x <= y <= n, 1 <= c <= 10,000, 1 <= p <= 3) The input ends with 0 0.
###output For each operation 4, output a single integer in one line representing the result. The answer may be quite large. You just need to calculate the remainder of the answer when divided by 10007.
###sample input 5 5 3 3 5 7 1 2 4 4 4 1 5 2 2 2 5 8 4 3 5 3 0 0
###sample output 307 7489
###tutorial 练习splay代替线段树
###cdoe 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
using namespace std;
const int mod=10007;
inline int M(int a,int b){return 1ll*a*b%mod;}
inline int M(int a,int b,int c){return M(M(a,b),c);}
inline int p2(int a){return M(a,a);}
inline int p3(int a){return M(a,a,a);}
inline int A(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int A(int a,int b,int c){return A(A(a,b),c);}
inline int A(int a,int b,int c,int d){return A(A(a,b,c),d);}
const int N=8e5+3;
int c[N][2],f[N],nie=N-1,tot;//树结构,几乎不用初始化
int nu[N],w[N],add[N],cov[N],mul[N];//值和懒惰标记结构,一定要赋初值，
int sz[N],s[N][3];//区间结构，不用赋予初值，
inline void pushup(int u){
sz[u]=sz[c[u][0]]+sz[c[u][1]]+nu[u];// assert(sz[nie]==0);
s[u][0]=A(s[c[u][0]][0],s[c[u][1]][0],w[u]);
s[u][1]=A(s[c[u][0]][1],s[c[u][1]][1],p2(w[u]));
s[u][2]=A(s[c[u][0]][2],s[c[u][1]][2],p3(w[u]));
}
inline void modify(int u,int _cov,int _mul,int _add){
if(u==nie) return;
if(_cov!=-1){
s[u][0]=M(sz[u],_cov);
s[u][1]=M(s[u][0],_cov);
s[u][2]=M(s[u][1],_cov);
cov[u]=_cov,mul[u]=1,add[u]=0;w[u]=_cov;
}
if(_mul!=1){
s[u][0]=M(s[u][0],_mul);
s[u][1]=M(s[u][1],p2(_mul));
s[u][2]=M(s[u][2],p3(_mul));
mul[u]=M(mul[u],_mul);
add[u]=M(add[u],_mul);
w[u]=M(w[u],_mul);
}
if(_add!=0){
s[u][2]=A(s[u][2],M(sz[u],p3(_add)),M(3,s[u][0],p2(_add)),M(3,s[u][1],_add));
s[u][1]=A(s[u][1],M(sz[u],p2(_add)),M(2,s[u][0],_add));
s[u][0]=A(s[u][0],M(sz[u],_add));
add[u]=A(add[u],_add);
w[u]=A(w[u],_add);
}
}
inline void pushdown(int u){
if(u==nie) return;
modify(c[u][0],cov[u],mul[u],add[u]);
modify(c[u][1],cov[u],mul[u],add[u]);
cov[u]=-1,mul[u]=1,add[u]=0;
}
inline void rotate(int x){// rotate后x的区间值是错误的，需要pushup(x)
int y=f[x],z=f[y],xis=c[y][1]==x,yis=c[z][1]==y;
f[x]=z,f[y]=x,f[c[x][xis^1]]=y;//father
c[z][yis]=x,c[y][xis]=c[x][xis^1],c[x][xis^1]=y;//son
pushup(y);
}
inline void splay(int x,int aim){//由于rotate后x的区间值不对，所以splay后x的区间值依旧不对，需要pushup(x)
while(f[x]!=aim){
int y=f[x],z=f[y];
if(z!=aim) (c[y][0]==x)^(c[z][0]==y)?rotate(x):rotate(y);// 同一个儿子先旋转y
rotate(x);
}
}
inline int id(int x,int u=c[nie][0]){ // 查询排名为x的数的节点下标 n个数 [1,n]
while(true){
pushdown(u);
if(sz[c[u][0]]>=x) u=c[u][0];
else if(sz[c[u][0]]+nu[u]<x) x-=sz[c[u][0]]+nu[u],u=c[u][1];
else return u;
}
}
int build(int father,int l,int r){// 把区间l,r建树，返回根(l+r)>>1
int u=(l+r)>>1;
f[u]=father;
c[u][0]=l<=u-1?build(u,l,u-1):nie;
c[u][1]=r>=u+1?build(u,u+1,r):nie;
pushup(u);
return u;
}
//究极读入挂
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
char ch=nc();int sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum;
}
int main(){
while(true){
int n=read(),m=read();
for(int i=0;i<=n+1;i++) w[i]=0,nu[i]=1,cov[i]=-1,mul[i]=1,add[i]=0;// 初始化节点信息 ,我们维护额外两个点的信息
c[nie][1]=f[nie]=nie,c[nie][0]=build(nie,0,n+1);
if(n==0&&m==0) break;
for(int i=0;i<m;i++){
int op=read(),x=id(1+read()-1),y=id(1+read()+1),p=read();
splay(x,nie), splay(y,x);
switch(op){
case 1:modify(c[y][0],-1,1,p);break;// add
case 2:modify(c[y][0],-1,p,0);break;// mulity
case 3:modify(c[y][0],p,1,0);break;// cover
case 4:printf("%d\n",s[c[y][0]][p-1]);break;
}
pushup(y), pushup(x);
}
}
}
uoj119
###name 决战圆锥曲线
###descirption 数学考试，一道圆锥曲线的题难住了你，你开始疯狂地笔算。但是，这题实在太难，于是你决定每种思路多尝试尝试。
你的思维过程可以转化为如下过程： 有一个随机数产生器，有个内部变量 x 初始时为 x0，每次产生随机数时它会将 x 变为 (100000005x+20150609)mod998244353，然后返回 ⌊x100⌋。（amodb 表示 a 除以 b的余数，该运算的优先级高于加减法。⌊α⌋表示 α向下取整后的结果。）初始时有 n个点，分别编号为 1,…,n，按编号从小到大顺序生成第 i个点的坐标：把横坐标赋为 i。产生一个随机数 y^，把纵坐标赋为 y^mod100001。有 m个操作，表示你的思路过程。操作共有三种：C：按顺序产生随机数 p,y，令 p=pmodn+1,y=ymod100001，然后把第 p 个点的纵坐标修改为 y。R：按顺序产生随机数 p,q ，令 p=min{pmodn+1,qmodn+1},q=max{pmodn+1,qmodn+1}，把编号大于等于 p 小于等于 q的点的纵坐标 y改为 100000−y。Q a b c：查询操作。按顺序产生随机数 p,q，令 p=min{pmodn+1,qmodn+1},q=max{pmodn+1,qmodn+1}，求最小的整数 t使得：对于所有编号大于等于 p小于等于 q的点 (x,y)都满足 ax+by+cxy≤t。（a,b,c均为非负整数）
###input 第一行三个整数 n,m,x0。保证 n,m≥1，0≤x0<998244353 且 x0≠340787122。 接下来 m行，每行表示一个操作，格式如前所述。
###output 对于每个查询操作输出一个整数表示最小的 t。
###sample input 3 3 2705443 C R Q 872784 195599 7
###sample output 13035048532
###hint 最开始三个点的坐标分别是 (1,91263),(2,33372),(3,10601)。 第一个操作把第三个点的坐标改成了 (3,94317)。 第二个操作修改了区间 [2,3]，第二个点变成了 (2,66628)，第三个点变成了 (3,5683)。 最后一个操作询问区间 [2,3]，可以发现最小的 t 是 13035048532。
###totuirial 对于\(x_i<x_j\)且\(y_i<y_j\)显然i不可能是答案，据此分析，每次取出y最大的点，然后就不用考虑左边的区间了，递归下去，复杂度\(nlogn^2\) 在线段树上启发式查询即可
###code 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
using namespace std;
const int maxn=1e5+5;
int ls[maxn<<1],rs[maxn<<1],rev[maxn<<1],mx[maxn<<1],mi[maxn<<1],a[maxn],tot;
void pushup(int&u){
mx[u]=max(mx[ls[u]],mx[rs[u]]);
mi[u]=min(mi[ls[u]],mi[rs[u]]);
}
void pushdown(int&u){
if(rev[u]){
swap(mx[ls[u]],mi[ls[u]]);
mx[ls[u]]=1e5-mx[ls[u]];
mi[ls[u]]=1e5-mi[ls[u]];
rev[ls[u]]^=1;
swap(mx[rs[u]],mi[rs[u]]);
mx[rs[u]]=1e5-mx[rs[u]];
mi[rs[u]]=1e5-mi[rs[u]];
rev[rs[u]]^=1;
rev[u]=0;
}
}
void build(int&u,int l,int r){
u=++tot;
rev[u]=0;
if(l==r){mx[u]=mi[u]=a[l];return;}
build(ls[u],l,ml); build(rs[u],mr,r);
pushup(u);
}
void update1(int&u,int l,int r,int q,int d){
if(l==r){mx[u]=mi[u]=d;return;}
pushdown(u);
if(q<=ml)update1(ls[u],l,ml,q,d);
if(q>=mr)update1(rs[u],mr,r,q,d);
pushup(u);
}
void update2(int&u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
rev[u]^=1;
swap(mx[u],mi[u]); mx[u]=1e5-mx[u]; mi[u]=1e5-mi[u];
return;
}
pushdown(u);
if(ql<=ml) update2(ls[u],l,ml,ql,qr);
if(mr<=qr) update2(rs[u],mr,r,ql,qr);
pushup(u);
}
int A,B,C;
long long f(int x,int y){return 1ll*x*A+1ll*y*B+1ll*x*y*C;}
long long query(int&u,int l,int r,int ql,int qr){
if(mx[u]==mi[u]) return f(r,mx[u]);
pushdown(u);
if(qr<=ml) return query(ls[u],l,ml,ql,qr);
else if(ql>=mr) return query(rs[u],mr,r,ql,qr);
else {
long long f1=f(ml,mx[ls[u]]),f2=f(r,mx[rs[u]]);
long long res=0;
if(f1>f2){
res=query(ls[u],l,ml,ql,qr);
if(f2>res) res=max(res,query(rs[u],mr,r,ql,qr));
}
else{
res=query(rs[u],mr,r,ql,qr);
if(f1>res) res=max(res,query(ls[u],l,ml,ql,qr));
}
return res;
}
}
int x;
int read(){
x=(100000005ll*x+20150609)%998244353;
return x/100;
}
int main(){
int n,m;
scanf("%d%d%d",&n,&m,&x);
for(int i=1;i<=n;i++) a[i]=read()%100001;
char s[10];
int rt; build(rt,1,n);
while(m--){
scanf("%s",s);
if(s[0]=='C'){
int p=read()%n+1;
int y=read()%100001;
update1(rt,1,n,p,y);
}
else if(s[0]=='R'){
int p=read()%n+1;
int q=read()%n+1;
if(p>q) swap(p,q);
update2(rt,1,n,p,q);
}
else{
scanf("%d%d%d",&A,&B,&C);
int p=read()%n+1;
int q=read()%n+1;
if(p>q) swap(p,q);
printf("%lld\n",query(rt,1,n,p,q));
}
}
}
P4121[wc2005]
###name 双面棋盘
###descirption 佳佳有一个 n 行 n 列的黑白棋盘，每个格子都有两面，一面白色，一面黑色。佳佳把棋盘平放在桌子上，因此每个格子恰好一面朝上，如下图所示： 
我们把每行从上到下编号为 1，2，3，……，n，各列从左到右编号为 1，2，3，……，n，则每个格子可以用棋盘坐标(x,y)表示。在上图中，有8个格子黑色朝上，另外17 个格子白色朝上。 如果两个同色格子有一条公共边，我们称这两个同色格子属于同一个连通块。上图共有 5 个黑色连通块和 3 个白色连通块。 佳佳可以每分钟将一个格子翻转（即白色变成黑色，黑色变成白色），然后计算当前有多少个黑色连通块和白色连通块，你能算得更快吗？
###input 输入文件的第一行包含一个正整数 n，为格子的边长。以下 n 行每行 n 个整数，非 0 即 1，表示初始状态。0 表示白色，1 表示黑色。下一行包含一个整数 m，表示操作的数目。以下 m 行每行两个整数 x, y (1 ≤ x, y ≤ n)，表示把坐标为(x,y)的格子翻转。
###output 输出文件包含 m 行，每行对应一个操作。该行包括两个整数 b, w，表示黑色区域和白色区域数目。
###sample input 5 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 2 3 2 2 3
###sample out 4 3 5 2
###hint ○1 ≤ n ≤ 200 ○1 ≤ m ≤ 10,000
###toturial 用线段树维护并查集，每个节点维护两个并查集，最上面的一行和最下面的一行，合并的时候根据四个并查集来维护即可，注意并查集的合并操作要仔细即可。
###code 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
using namespace std;
struct DSU{
int f[810];
inline void ini(int n){rep(i,1,n)f[i]=i;}
inline int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void join(int x,int y){f[find(x)]=find(y);}
};
int mp[222][222];
int ls[210*2],rs[210*2],tot,n;
struct treenode{
DSU d;
int sz[2];
}tr[210*2];
void build(treenode&res,int*a){
res.d.ini(n+n);
rep(i,2,n) if(a[i]==a[i-1]) res.d.join(i,i-1),res.d.join(n+i,n+i-1);
rep(i,1,n) res.d.join(i+n,i);
res.sz[0]=res.sz[1]=0;
static int vis[220];
rep(i,1,n) vis[i]=0;
rep(i,1,n) if(!vis[res.d.find(i)]) res.sz[a[i]]++,vis[res.d.find(i)]=1;
}
void merge(treenode&a,treenode&b,int c1,int c2){
a.sz[0]=a.sz[0]+b.sz[0];
a.sz[1]=a.sz[1]+b.sz[1];
rep(i,1,2*n) a.d.f[i+2*n]=b.d.f[i]+2*n;
DSU&dsu=a.d;
rep(i,1,n) if(mp[c1][i]==mp[c2][i]){
if(dsu.find(i+n)!=dsu.find(i+2*n)){
dsu.join(i+n,i+2*n);
a.sz[mp[c1][i]]--;
}
}
rep(i,1,n) if(dsu.find(i)>n&&dsu.find(i)<=3*n) dsu.f[dsu.find(i)]=i,dsu.f[i]=i;
rep(i,3*n+1,4*n) if(dsu.find(i)>n&&dsu.find(i)<=3*n) dsu.f[dsu.find(i)]=i,dsu.f[i]=i;
rep(i,3*n+1,4*n) dsu.f[i-2*n]=dsu.f[i]>n?dsu.f[i]-2*n:dsu.f[i];
}
void build(int&u,int l,int r){
u=++tot;
if(l==r){
build(tr[u],mp[l]);
return;
}
build(ls[u],l,ml);
build(rs[u],mr,r);
tr[u]=tr[ls[u]];
merge(tr[u],tr[rs[u]],ml,mr);
}
void update(int&u,int l,int r,int q){
if(l==r){
build(tr[u],mp[l]);
return;
}
if(q<=ml) update(ls[u],l,ml,q);
else update(rs[u],mr,r,q);
tr[u]=tr[ls[u]];
merge(tr[u],tr[rs[u]],ml,mr);
}
int main(){
scanf("%d",&n);
rep(i,1,n)rep(j,1,n) scanf("%d",&mp[i][j]);
int rt; build(rt,1,n);
int m;scanf("%d",&m);
while(m--){
int x,y;scanf("%d%d",&x,&y);
mp[x][y]^=1;
update(rt,1,n,x);
printf("%d %d\n",tr[1].sz[1],tr[1].sz[0]);
}
}