ACM►刷题实战►hdu

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,j,k) for(ll i=(j);i<=(k);i++)

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));// 子集中大于一个元素
    }
}
ACM►刷题实战►hdu

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
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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
namespace math{
    const int maxn=1e7+7;
    bool no_pri[maxn]={0,1,0};
    int pri[664579+100],low[maxn],phi[maxn];
    void f_ini(){
        for(int i=2;i<maxn;i++){
            if(!no_pri[i]) low[i]=pri[++pri[0]]=i;
            for(int j=1;1ll*pri[j]*i<maxn;j++){
                no_pri[pri[j]*i]=1;
                if(i%pri[j]==0) {
                    low[pri[j]*i]=low[i]*pri[j];
                    break;
                }
                else low[pri[j]*i]=pri[j];
            }
        }

        phi[1]=1;
        for(int i=1;i<=pri[0];i++){
            for(ll mul=pri[i],ct=1;mul<maxn;mul*=pri[i],ct++){
                phi[mul]=mul/pri[i]*(pri[i]-1);// 改这里
            }
        }

        for(int i=2;i<maxn;i++){
            for(int j=1;1ll*pri[j]*i<maxn;j++){
                int x=low[i*pri[j]], y=i*pri[j]/x;
                phi[x*y]=phi[x]*phi[y];
                if(i%pri[j]==0) break;
            }
        }
    }
}

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=3e5+5;
int a[maxn];
int ls[maxn*2],rs[maxn*2],tot;// 树结构
int cov[maxn*2];// 懒惰标记结构
ll sum[maxn*2];int mi[maxn*2],mx[maxn*2];// 区间结构

inline void modify(int&u,int l,int r,int cov_){// 这个函数要注意重写
    if(cov_!=-1){
        cov[u]=cov_;
        sum[u]=1ll*cov_*(r-l+1);
        mi[u]=mx[u]=cov_;
    }
}

inline void push_down(int u,int l,int r){
    modify(ls[u],l,ml,cov[u]);// 这行要注意重写
    modify(rs[u],mr,r,cov[u]);// 这行要注意重写
    cov[u]=-1;// 这行要注意重写
}

inline void pushup(int u,int l,int r){
    mi[u]=min(mi[ls[u]],mi[rs[u]]);// 这行要注意重写
    mx[u]=max(mx[ls[u]],mx[rs[u]]);// 这行要注意重写
    sum[u]=sum[ls[u]]+sum[rs[u]];// 这行要注意重写
}

void updatecov(int u,int l,int r,int ql,int qr,int d){//
    if(ql<=l&&r<=qr){
        modify(u,l,r,d);// 这行要注意重写
        return;
    }
    push_down(u,l,r);
    if(ml>=ql) updatecov(ls[u],l,ml,ql,qr,d);
    if(mr<=qr) updatecov(rs[u],mr,r,ql,qr,d);
    pushup(u,l,r);
}

void updatephi(int u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr&&mi[u]==mx[u]){
        modify(u,l,r,math::phi[mi[u]]);// 这行要注意重写
        return;
    }
    push_down(u,l,r);
    if(ml>=ql) updatephi(ls[u],l,ml,ql,qr);
    if(mr<=qr) updatephi(rs[u],mr,r,ql,qr);
    pushup(u,l,r);
}

ll query(int u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[u];// 这行要注意重写
    push_down(u,l,r);
    ll ret=0;// 这行要注意重写
    if(ml>=ql) ret+=query(ls[u],l,ml,ql,qr);// 这行要注意重写
    if(mr<=qr) ret+=query(rs[u],mr,r,ql,qr);// 这行要注意重写
    return ret;
}

void build(int&u,int l,int r){
    u=++tot;
    cov[u]=-1;
    if(l==r) sum[u]=mi[u]=mx[u]=a[l];
    else{
        build(ls[u],l,ml);
        build(rs[u],mr,r);
        pushup(u,l,r);
    }
}

int read(){int x;scanf("%d",&x);return x;}

int main(){
    math::f_ini();
    int t=read();
    while(t--){
        int n=read(),m=read();
        for(int i=1;i<=n;i++) a[i]=read();
        tot=0;
        int rt; build(rt,1,n);
        for(int i=1;i<=m;i++){
            int op=read(),l=read(),r=read();
            switch(op){
                case 1:updatephi(rt,1,n,l,r);break;
                case 2:updatecov(rt,1,n,l,r,read());break;
                default:printf("%lld\n",query(rt,1,n,l,r));
            }
        }
    }
}

code-splay

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
namespace math{
    const int maxn=1e7+7;
    bool no_pri[maxn]={0,1,0};
    int pri[664579+100],low[maxn],phi[maxn];
    void f_ini(){
        for(int i=2;i<maxn;i++){
            if(!no_pri[i]) low[i]=pri[++pri[0]]=i;
            for(int j=1;1ll*pri[j]*i<maxn;j++){
                no_pri[pri[j]*i]=1;
                if(i%pri[j]==0) {
                    low[pri[j]*i]=low[i]*pri[j];
                    break;
                }
                else low[pri[j]*i]=pri[j];
            }
        }

        phi[1]=1;
        for(int i=1;i<=pri[0];i++){
            for(ll mul=pri[i],ct=1;mul<maxn;mul*=pri[i],ct++){
                phi[mul]=mul/pri[i]*(pri[i]-1);// 改这里
            }
        }

        for(int i=2;i<maxn;i++){
            for(int j=1;1ll*pri[j]*i<maxn;j++){
                int x=low[i*pri[j]], y=i*pri[j]/x;
                phi[x*y]=phi[x]*phi[y];
                if(i%pri[j]==0) break;
            }
        }
    }
}

const int N=3e5+3;
int c[N][2],f[N],stk[N],nie=N-1,tot;//树结构,几乎不用初始化
int nu[N],w[N],cov[N];//值和懒惰标记结构,一定要赋初值，
int sz[N],mx[N],mi[N]; long long s[N];//区间结构，不用赋予初值，

inline void pushfrom(int u,int son){// assert(son!=nie)
    sz[u]+=sz[son],mx[u]=max(mx[u],mx[son]),mi[u]=min(mi[u],mi[son]),s[u]+=s[son];
}
inline void pushup(int u){// assert(u!=nie)
    sz[u]=nu[u],mi[u]=mx[u]=w[u],s[u]=1ll*w[u]*nu[u];
    if(c[u][0]!=nie) pushfrom(u,c[u][0]);
    if(c[u][1]!=nie) pushfrom(u,c[u][1]);
}
inline void modify(int u,int _cov){// assert(u!=nie)
    if(_cov!=-1) {
        w[u]=mx[u]=mi[u]=_cov;
        s[u]=1ll*sz[u]*_cov;
    }
}
inline void pushdown(int u){
    if(u==nie||cov[u]==-1) return;
    if(c[u][0]!=nie) modify(c[u][0],cov[u]);
    if(c[u][1]!=nie) modify(c[u][1],cov[u]);
    cov[u]=-1;
}
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);
    }
}
void del(int u){// del compress newnode decompress 是一套独立的函数，可以直接删除，也可以与上面的代码共存
    stk[++stk[0]]=u;
    if(c[u][0]!=nie) del(c[u][0]);
    if(c[u][1]!=nie) del(c[u][1]);
}
inline void compress(int u){ // 压缩区间，将节点丢进栈 assert(u!=nie)
    if(c[u][0]!=nie) del(c[u][0]);
    if(c[u][1]!=nie) del(c[u][1]);
    c[u][0]=c[u][1]=nie,nu[u]=sz[u];
}
inline int newnode(int father,int val,int siz){//
    int u=stk[0]==0?(++tot):stk[stk[0]--];
    f[u]=father,c[u][0]=c[u][1]=nie; //树结构
    w[u]=val,nu[u]=siz,cov[u]=-1; //值和懒惰标记结构,
    sz[u]=siz,mi[u]=mx[u]=val,s[u]=1ll*val*siz;//区间结构
    return u;
}
inline void decompress(int x,int u){// 解压区间并提取第x个值 assert(u!=nie)
    int ls=c[u][0],rs=c[u][1];
    if(x>1) c[u][0]=newnode(u,w[u],x-1),c[c[u][0]][0]=ls;
    if(x<nu[u]) c[u][1]=newnode(u,w[u],nu[u]-x),c[c[u][1]][1]=rs;
    nu[u]=1;
}
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{
            if(nu[u]!=1) decompress(x,u);
            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;
}

void updatephi(int u){
    pushdown(u);
    if(c[u][0]!=nie) updatephi(c[u][0]);
    if(c[u][1]!=nie) updatephi(c[u][1]);
    w[u]=math::phi[w[u]];
    pushup(u);
    if(nu[u]!=1&&mi[u]==mx[u]) compress(u);
}

int read(){int x;scanf("%d",&x);return x;}

int main(){
    math::f_ini();
    int t=read();
    while(t--){
        int n=read(),m=read();
        for(int i=0;i<=n+1;i++) nu[i]=1,cov[i]=-1;
        for(int i=1;i<=n;i++) w[i]=read();
        c[nie][1]=f[nie]=nie;c[nie][0]=build(nie,0,n+1);// 左边放一个 右边放一个 刚刚好
        tot=n+1;stk[0]=0;// init rubbish

        for(int i=1;i<=m;i++){
            int op=read(),l=read(),r=read();// [1,n]->[2,n+1]
            int x=id(1+l-1),y=id(1+r+1);
            splay(x,nie);splay(y,x);
            switch(op){
                case 1:updatephi(c[y][0]);break;
                case 2:modify(c[y][0],read()),compress(c[y][0]);break;
                default:printf("%lld\n",s[c[y][0]]);
            }
            pushup(y),pushup(x);
        }
    }
}
ACM►学习笔记►平衡树

splay 

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
//初始化时要初始化tot和stk[0]
const int N=3e5+3;
int c[N][2],f[N],stk[N],nie=N-1,tot;//树结构,几乎不用初始化
int nu[N],w[N],cov[N];//值和懒惰标记结构,一定要赋初值，
int sz[N],mx[N],mi[N]; long long s[N];//区间结构，不用赋予初值，

inline void pushfrom(int u,int son){// assert(son!=nie)
    sz[u]+=sz[son],mx[u]=max(mx[u],mx[son]),mi[u]=min(mi[u],mi[son]),s[u]+=s[son];
}
inline void pushup(int u){// assert(u!=nie)
    sz[u]=nu[u],mi[u]=mx[u]=w[u],s[u]=1ll*w[u]*nu[u];
    if(c[u][0]!=nie) pushfrom(u,c[u][0]);
    if(c[u][1]!=nie) pushfrom(u,c[u][1]);
}
inline void modify(int u,int _cov){// assert(u!=nie)
    if(_cov!=-1) {
        w[u]=mx[u]=mi[u]=_cov;
        s[u]=1ll*sz[u]*_cov;
    }
}
inline void pushdown(int u){
    if(u==nie||cov[u]==-1) return;
    if(c[u][0]!=nie) modify(c[u][0],cov[u]);
    if(c[u][1]!=nie) modify(c[u][1],cov[u]);
    cov[u]=-1;
}
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);
    }
}
void del(int u){// del compress newnode decompress 是一套独立的函数，可以直接删除，也可以与上面的代码共存
    stk[++stk[0]]=u;
    if(c[u][0]!=nie) del(c[u][0]);
    if(c[u][1]!=nie) del(c[u][1]);
}
inline void compress(int u){ // 压缩区间，将节点丢进栈 assert(u!=nie)
    if(c[u][0]!=nie) del(c[u][0]);
    if(c[u][1]!=nie) del(c[u][1]);
    c[u][0]=c[u][1]=nie,nu[u]=sz[u];
}
inline int newnode(int father,int val,int siz){//
    int u=stk[0]==0?(++tot):stk[stk[0]--];
    f[u]=father,c[u][0]=c[u][1]=nie; //树结构
    w[u]=val,nu[u]=siz,cov[u]=-1; //值和懒惰标记结构,
    sz[u]=siz,mi[u]=mx[u]=val,s[u]=1ll*val*siz;//区间结构
    return u;
}
inline void decompress(int x,int u){// 解压区间并提取第x个值 assert(u!=nie)
    int ls=c[u][0],rs=c[u][1];
    if(x>1) c[u][0]=newnode(u,w[u],x-1),c[c[u][0]][0]=ls;
    if(x<nu[u]) c[u][1]=newnode(u,w[u],nu[u]-x),c[c[u][1]][1]=rs;
    nu[u]=1;
}
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{
            if(nu[u]!=1) decompress(x,u);
            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;
}

void updatephi(int u){
    pushdown(u);
    if(c[u][0]!=nie) updatephi(c[u][0]);
    if(c[u][1]!=nie) updatephi(c[u][1]);
    w[u]=math::phi[w[u]];
    pushup(u);
    if(nu[u]!=1&&mi[u]==mx[u]) compress(u);
}
ACM►学习笔记►平衡树

线段树 

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
#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=3e5+5;
int a[maxn];
int ls[maxn*2],rs[maxn*2],tot;// 树结构
int cov[maxn*2];// 懒惰标记结构
ll sum[maxn*2];int mi[maxn*2],mx[maxn*2];// 区间结构

inline void modify(int&u,int l,int r,int cov_){// 这个函数要注意重写
    if(cov_!=-1){// 这行要注意重写
        cov[u]=cov_;// 这行要注意重写
        sum[u]=1ll*cov_*(r-l+1);// 这行要注意重写
        mi[u]=mx[u]=cov_;// 这行要注意重写
    }
}

inline void push_down(int u,int l,int r){
    modify(ls[u],l,ml,cov[u]);// 这行要注意重写
    modify(rs[u],mr,r,cov[u]);// 这行要注意重写
    cov[u]=-1;// 这行要注意重写
}

inline void pushup(int u,int l,int r){
    mi[u]=min(mi[ls[u]],mi[rs[u]]);// 这行要注意重写
    mx[u]=max(mx[ls[u]],mx[rs[u]]);// 这行要注意重写
    sum[u]=sum[ls[u]]+sum[rs[u]];// 这行要注意重写
}

void updatecov(int u,int l,int r,int ql,int qr,int d){//
    if(ql<=l&&r<=qr){// 不要改写为 if(mi[u]==mx[u]) 即使想写也要这样 if(ql<=l&&r<=qr&&mi[u]==mx[u])
        modify(u,l,r,d);// 这行要注意重写
        return;
    }
    push_down(u,l,r);
    if(ml>=ql) updatecov(ls[u],l,ml,ql,qr,d);
    if(mr<=qr) updatecov(rs[u],mr,r,ql,qr,d);
    pushup(u,l,r);
}

void updatephi(int u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr&&mi[u]==mx[u]){// 这行要注意重写
        modify(u,l,r,math::phi[mi[u]]);// 这行要注意重写
        return;
    }
    push_down(u,l,r);
    if(ml>=ql) updatephi(ls[u],l,ml,ql,qr);
    if(mr<=qr) updatephi(rs[u],mr,r,ql,qr);
    pushup(u,l,r);
}

ll query(int u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[u];// 这行要注意重写
    push_down(u,l,r);
    ll ret=0;// 这行要注意重写
    if(ml>=ql) ret+=query(ls[u],l,ml,ql,qr);// 这行要注意重写
    if(mr<=qr) ret+=query(rs[u],mr,r,ql,qr);// 这行要注意重写
    return ret;
}

void build(int&u,int l,int r){
    u=++tot;
    cov[u]=-1;
    if(l==r) sum[u]=mi[u]=mx[u]=a[l];
    else{
        build(ls[u],l,ml);
        build(rs[u],mr,r);
        pushup(u,l,r);
    }
}
ACM►刷题实战►hdu

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
#include<bits/stdc++.h>
using namespace std;

#define get64(a,b) ((a)*2000000000ll+(b))
typedef pair<int,int> pii;
#define __int64 long long

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",&times);
    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;
    }
}
ACM►刷题实战►bzoj

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
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
#include<bits/stdc++.h>
using namespace std;

int n;
namespace segtree{
    const int maxn=4e5+5;
    int ls[maxn*20],rs[maxn*20],siz[maxn*20];
    int rt[maxn],a[maxn],tot,vis[maxn];

    void update2(int&u,int l,int r,int pos,int val){
        if(u==0) u=++tot,assert(u<maxn*20),ls[u]=rs[u]=siz[u]=0;
        siz[u]+=val;
        if(l==r) return;
        int mid=(l+r)>>1;
        if(pos<=mid) update2(ls[u],l,mid,pos,val);
        else update2(rs[u],mid+1,r,pos,val);
    }
    void update(int x,int w){// a[x]=w
        if(vis[x]==1) update2(rt[a[x]],1,n,x,-1);
        a[x]=w; vis[x]=1;
        update2(rt[w],1,n,x,1);
    }

    int query2(int u,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr) return siz[u];
        int res=0,mid=(l+r)>>1;
        if(ql<=mid) res+=query2(ls[u],l,mid,ql,qr);
        if(mid+1<=qr) res+=query2(rs[u],mid+1,r,ql,qr);
        return res;
    }
    int query(int l,int r,int w){// a[?]=w
        return query2(rt[w],1,n,l,r);
    }
}

const int maxn=1e5+5;
int to[maxn<<1],nex[maxn<<1],head[maxn],w[maxn],cnt;
void ini(){cnt=-1;for(int i=0;i<=n;i++) head[i]=-1;}
void add_edge(int u,int v){to[++cnt]=v;nex[cnt]=head[u];head[u]=cnt;}

int dep[maxn],dad[maxn],siz[maxn],son[maxn],chain[maxn],dfn[maxn];//
void dfs1(int u,int father){//dfs1(1,0)
    dep[u]=dep[father]+1;//ini  because dep[0]=1
    dad[u]=father, siz[u]=1, son[u]=-1;
    for(int i=head[u];~i;i=nex[i]){
        int v=to[i];
        if(v==father)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v;
    }
}
void dfs2(int u,int s,int&step){
    dfn[u]=++step;
    chain[u]=s;
    if(son[u]!=-1) dfs2(son[u],s,step);
    for(int i=head[u];~i;i=nex[i]){
        int v=to[i];
        if(v!=son[u]&&v!=dad[u]) dfs2(v,v,step);
    }
}
int query(int x,int y,int k){
    int res=0;
    while(chain[x]!=chain[y]){
        if(dep[chain[x]]<dep[chain[y]]) swap(x,y); //dep[chain[x]]>dep[chain[y]]
        res+=segtree::query(dfn[chain[x]],dfn[x],k);// [左，右，值]
        x=dad[chain[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);// dep[x]<dep[y]
    return res+segtree::query(dfn[x],dfn[y],k);// [左,右,值]
}

vector<int>disc;
int getid(int x){return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;}

char op[maxn*2];
int x[maxn*2],y[maxn*2],z[maxn*2];

int main(){
    int q;scanf("%d%d",&n,&q);
    ini();
    for(int i=1;i<=n;i++) scanf("%d",&w[i]),disc.push_back(w[i]);
    for(int i=2;i<=n;i++) {
        int u,v; scanf("%d%d",&u,&v);
        add_edge(u,v);add_edge(v,u);
    }
    for(int i=1;i<=q;i++){
        scanf(" %c%d%d",op+i,x+i,y+i);
        if(op[i]=='Q') scanf("%d",z+i),disc.push_back(z[i]);
        else disc.push_back(y[i]);
    }
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());

    int step=0;
    dfs1(1,0),dfs2(1,0,step);
    for(int i=1;i<=n;i++) segtree::update(dfn[i],getid(w[i]));
    for(int i=1;i<=q;i++){
        if(op[i]=='Q') {
            int id=getid(z[i]);
            printf("%d\n",disc[id-1]==z[i]?query(x[i],y[i],id):0);
        }
        else segtree::update(dfn[x[i]],getid(y[i]));
    }
}
ACM►刷题实战►hdu

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
#include<bits/stdc++.h>
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);
        }
    }
}
ACM►刷题实战►uoj

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=p^modn+1,y=y^mod100001，然后把第 p 个点的纵坐标修改为 y。R：按顺序产生随机数 p^,q^
，令 p=min{p^modn+1,q^modn+1},q=max{p^modn+1,q^modn+1}，把编号大于等于 p 小于等于 q的点的纵坐标 y改为 100000−y。Q a b c：查询操作。按顺序产生随机数 p^,q^，令 p=min{p^modn+1,q^modn+1},q=max{p^modn+1,q^modn+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
#include<bits/stdc++.h>
using namespace std;

#define ml ((l+r)>>1)
#define mr (ml+1)

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));
        }
    }
}

ACM►刷题实战►洛谷

P4121[wc2005]

###name
双面棋盘

###descirption
佳佳有一个 n 行 n 列的黑白棋盘，每个格子都有两面，一面白色，一面黑色。佳佳把棋盘平放在桌子上，因此每个格子恰好一面朝上，如下图所示：
wtf
我们把每行从上到下编号为 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
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=(j);i<=(k);i++)
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];

#define ml ((l+r)>>1)
#define mr (ml+1)
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]);
    }
}
ACM►刷题实战►CodeForces

Codeforces Round #172 (Div. 1) - D

name

k-Maximum Subsequence Sum

descirption

time limit per test 4 seconds
memory limit per test 256 megabytes
Consider integer sequence $a_1, a_2, …, a_n$. You should run queries of two types:
The query format is “0 i val”. In reply to this query you should make the following assignment: $a_i$ = val.
The query format is “1 l r k”. In reply to this query you should print the maximum sum of at most k non-intersecting subsegments of sequence $a_l, a_{l + 1}, …, a_r$. Formally, you should choose at most k pairs of integers $(x_1, y_1), (x_2, y_2), …, (x_t, y_t) (l ≤ x_1 ≤ y_1 < x_2 ≤ y_2 < … < x_t ≤ y_t ≤ r; t ≤ k)$ such that the sum $a_{x_1
} + a_{x_1 + 1} + … + a_{y_1} + a_{x_2} + a_{x_2 + 1} + … + a_{y_2} + … + a_{x_t} + a_{x_t + 1} + … + a_{y_t}$ is as large as possible. Note that you should choose at most k subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero

input

The first line contains integer $n (1 ≤ n ≤ 10^5)$, showing how many numbers the sequence has. The next line contains n integers a1, a2, …, an (|ai| ≤ 500).
The third line contains integer $m (1 ≤ m ≤ 10^5)$ — the number of queries. The next m lines contain the queries in the format, given in the statement.
All changing queries fit into limits: 1 ≤ i ≤ n, |val| ≤ 500.
All queries to count the maximum sum of at most k non-intersecting subsegments fit into limits: 1 ≤ l ≤ r ≤ n, 1 ≤ k ≤ 20. It is guaranteed that the number of the queries to count the maximum sum of at most k non-intersecting subsegments doesn’t exceed 10000.

output

For each query to count the maximum sum of at most k non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.

sample input

1
2
3
4
5
6
9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3

sample output

1
2
3
17
25
0

sample input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1

sample output

1
2
3
4
5
6
7
8
9
14
11
15
0
15
26
18
23
8

hint

In the first query of the first example you can select a single pair (1, 9). So the described sum will be 17.

Look at the second query of the first example. How to choose two subsegments? (1, 3) and (7, 9)? Definitely not, the sum we could get from (1, 3) and (7, 9) is 20, against the optimal configuration (1, 7) and (9, 9) with 25.

The answer to the third query is 0, we prefer select nothing if all of the numbers in the given interval are negative.

toturial

先考虑k=1的情况, 我么你可以直接用线段树来维护，这是一个经典问题，但是当k>1的时候，我们可以这样来做，我们做k次下诉操作，取出最大字段和，然后将这一段数乘以-1，直到最大字段和为负或者执行了k次操作，如此我们就能得到最大k字段和。正确性可以用费用流来证明。

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
#include<bits/stdc++.h>
using namespace std;

#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define ml ((l+r)>>1)
#define mr (ml+1)

inline void swap2(int&a,int&b){a*=-1;b*=-1;swap(a,b);}
struct sub{
    int maxl,maxlat;
    int minl,minlat;
    int maxr,maxrat;
    int minr,minrat;
    int maxv,maxvlat,maxvrat;
    int minv,minvlat,minvrat;
    int sum,l,r;
    void mul(int val){
        if(val==-1){
            swap2(maxl,minl);
            swap2(maxr,minr);
            swap2(maxv,minv);
            swap(maxlat,minlat);
            swap(maxrat,minrat);
            swap(maxvlat,minvlat);
            swap(maxvrat,minvrat);
            sum*=-1;
        }
    }
    void cov(int val){
        if(val>0){
            maxl=maxr=maxv=sum=val*(r-l+1);
            maxlat=maxvrat=r;
            maxrat=maxvlat=l;
            minl=minr=minv=0;
        }
        else{
            minl=minr=minv=sum=val*(r-l+1);
            minlat=minvrat=r;
            minrat=minvlat=l;
            maxl=maxr=maxv=0;
        }
    }
};
inline sub merge(const sub&a,const sub&b){
    if(a.l>a.r) return b;
    sub res=a;
    res.maxr=b.maxr;
    res.minr=b.minr;
    res.maxrat=b.maxrat;
    res.minrat=b.minrat;
    if(res.maxl<a.sum+b.maxl) res.maxl=a.sum+b.maxl,res.maxlat=b.maxlat;
    if(res.minl>a.sum+b.minl) res.minl=a.sum+b.minl,res.minlat=b.minlat;
    if(res.maxr<b.sum+a.maxr) res.maxr=b.sum+a.maxr,res.maxrat=a.maxrat;
    if(res.minr>b.sum+a.minr) res.minr=b.sum+a.minr,res.minrat=a.minrat;
    if(res.maxv<b.maxv) res.maxv=b.maxv,res.maxvlat=b.maxvlat,res.maxvrat=b.maxvrat;
    if(res.maxv<a.maxr+b.maxl) res.maxv=a.maxr+b.maxl,res.maxvlat=a.maxrat,res.maxvrat=b.maxlat;
    if(res.minv>b.minv) res.minv=b.minv,res.minvlat=b.minvlat,res.minvrat=b.minvrat;
    if(res.minv>a.minr+b.minl) res.minv=a.minr+b.minl,res.minvlat=a.minrat,res.minvrat=b.minlat;
    res.sum=a.sum+b.sum, res.l=a.l, res.r=b.r;
    return res;
}

const int maxn=1e5+5;
int ls[maxn*2],rs[maxn*2],cov[maxn*2],mul[maxn*2],a[maxn],tot;
sub s[maxn*2];

void pushup(int&u){s[u]=merge(s[ls[u]],s[rs[u]]);}
void pushdown(int&u,int l,int r){
    if(cov[u]<2e9){
        cov[ls[u]]=cov[rs[u]]=cov[u];
        mul[ls[u]]=mul[rs[u]]=1;
        s[ls[u]].cov(cov[u]);
        s[rs[u]].cov(cov[u]);
        cov[u]=2e9;
    }
    if(mul[u]==-1) {
        mul[ls[u]]*=mul[u];
        mul[rs[u]]*=mul[u];
        s[ls[u]].mul(mul[u]);
        s[rs[u]].mul(mul[u]);
        mul[u]=1;
    }
}

void build(int&u,int l,int r){
    u=++tot;
    cov[u]=2e9;
    mul[u]=1;
    s[u].l=l;
    s[u].r=r;
    if(l==r){
        s[u].cov(a[l]);
        return;
    }
    build(ls[u],l,ml);// ls[u]
    build(rs[u],mr,r);// rs[u]
    pushup(u);// s[u]
}

void update(int&u,int l,int r,int ql,int qr,int d,int flag){
    if(ql<=l&&r<=qr){
        if(flag==0) {//cover
            cov[u]=d;
            mul[u]=1;
            s[u].cov(d);
        }
        else{// multi
            mul[u]*=d;
            s[u].mul(d);
        }
        return;
    }
    pushdown(u,l,r);
    if(ql<=ml) update(ls[u],l,ml,ql,qr,d,flag);
    if(mr<=qr) update(rs[u],mr,r,ql,qr,d,flag);
    pushup(u);
}


sub query(int&u,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return s[u];
    pushdown(u,l,r);
    sub res; res.l=res.r+1;
    if(ql<=ml) res=merge(res,query(ls[u],l,ml,ql,qr));
    if(mr<=qr) res=merge(res,query(rs[u],mr,r,ql,qr));
    return res;
}

int main(){
    int n;scanf("%d",&n);
    rep(i,1,n) scanf("%d",&a[i]);
    tot=0;
    int rt; build(rt,1,n);
    int m;scanf("%d",&m);
    int op,i,val,l,r,k;
    while(m--){
        scanf("%d",&op);
        if(op==0){
            scanf("%d%d",&i,&val);
            update(rt,1,n,i,i,val,0);
        }
        if(op==1){
            scanf("%d%d%d",&l,&r,&k);
            int ans=0;
            vector<int>L,R;
            while(k--){
                sub res=query(rt,1,n,l,r);
                if(res.maxv<=0) break;
                ans+=res.maxv;
                L.push_back(res.maxvlat);
                R.push_back(res.maxvrat);
                update(rt,1,n,L.back(),R.back(),-1,1);
            }
            while(!L.empty()){
                update(rt,1,n,L.back(),R.back(),-1,1);
                L.pop_back();R.pop_back();
            }
            printf("%d\n",ans);
        }
    }
}