XXII Open Cup. Grand Prix of Korea

C.Equivalent Pipelines

首先可以看到，树的数量很多，所以只能给每个树一个hash值，从而通过hash是否相同判断是否同类

这里可以首先意识到，对于两棵树而言，先把所有边断开，从大到小开始依次加边，一次操作只加相同长度的边，如果能保证每次连起来的若干个新的连通分量内部的点都是一样的，那么就符合要求。

通过归纳法可以容易得出：对于所有长度为w的边，我们记录这个长度w，还有连接发生前每个连通分量中编号最小的点，以及通过这条边连成的新连通分量中编号最小的点，形成一个三元组；如果对于两棵树而言，它们的三元组的集合完全一样，则一定满足上述条件。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e5+5;
const ll mod=998244353;
int d,n,tot;
struct Edge{
    int u,v,w;
};
vector<Edge>e;
set<ll>st;
map<int,int>mp;
map<set<ll>,int>dsu;
int vis[maxn],fa[maxn];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
ll hsh(ll x,ll y,ll z){
    return x*maxn*maxn+y*maxn+z;
}
void solve(){
    vector<pii>vec;
    for(int i=0;i<e.size();i++){
        int fau=find(e[i].u);
        int fav=find(e[i].v);
        if(fau>fav)swap(fau,fav);
        //fa[fav]=fau;
        // ll cur=hsh(fau,fav,mp[e[i].w]);
        // st.insert(cur);
        vec.push_back({fau,fav});
       // printf("##%d %d %d\n",fau,fav,e[i].w);
        if(i==e.size()-1||e[i].w!=e[i+1].w){
            // int pos=i;
            for(auto p:vec){
                int fau=find(p.first),fav=find(p.second);
                if(fau>fav)swap(fau,fav);
                fa[fav]=fau;
            }
            for(auto p:vec){
                ll cur1=hsh(find(p.first),p.first,e[i].w);
                ll cur2=hsh(find(p.second),p.second,e[i].w);
                st.insert(cur1);
                st.insert(cur2);
            }
            // while(pos>=0&&(pos==i||e[pos].w==e[pos+1].w)){
            //     int fau=find(e[pos].u),fav=find(e[pos].v);
            //     if(fau<fav)fa[fav]=fau;
            //     else fa[fau]=fav;
            //     pos--;
            // }
            vec.clear();
        }
    }
}
bool cmp(Edge x,Edge y){
    return x.w>y.w;
}
int main(){
    scanf("%d%d",&d,&n);
    for(int i=1;i<=d;i++){
        e.clear();st.clear();
        for(int j=1;j<=n;j++){
            fa[j]=j;
            //mp[i]=++tot;vis[i]=tot;
        }
        for(int j=1;j<n;j++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            // e[u].push_back({v,w});
            // e[v].push_back({u,w});
            if(!mp[w])mp[w]=++tot;
            if(u>v)swap(u,v);
            e.push_back({u,v,w});
        }
        sort(e.begin(),e.end(),cmp);
        solve();
        if(!dsu.count(st)){
            dsu[st]=i;
            printf("%d ",i);
        }
        else printf("%d ",dsu[st]);
    }
    return 0;
}

G.Lamb’s Respite

这道题使用到了很少见的区间查询方式，即通过记录前缀和后缀和求出区间内部连续最值和。

然而这个题目的难点在于，如何使用生命值有上限，即HH，这一条件。这里我们只需要求出连续和小于−H-H的一段即可（这里可以通过反证法证明）。

注意这道题要处理三段区间，即被Lamb’s Respite分隔开的两段区间，再加上Lamb’s Respite内部的区间，有两段区间的起始生命值并不一定是HH，所以要把这个影响加在区间的开头

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=3e5+5;
const ll mod=998244353;
int n,q;
ll a[maxn];
struct node{
    ll pre,suf,mn,sum;
}t[maxn<<2];
void push_up(int rt){
    t[rt].pre=min(t[rt<<1].pre,t[rt<<1].sum+t[rt<<1|1].pre);
    t[rt].suf=min(t[rt<<1|1].suf,t[rt<<1].suf+t[rt<<1|1].sum);
    t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
    t[rt].mn=min(min(t[rt<<1].mn,t[rt<<1|1].mn),t[rt<<1].suf+t[rt<<1|1].pre);
}
void build(int rt,int l,int r){
    int mid=l+r>>1;
    if(l==r){
        t[rt].pre=t[rt].suf=t[rt].mn=t[rt].sum=a[l];
        return ;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    push_up(rt);
}
ll query_sum(int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(xl==l&&xr==r){
        return t[rt].sum;
    }
    ll res=0;
    if(xl<=mid)res+=query_sum(rt<<1,l,mid,xl,min(xr,mid));
    if(xr>mid)res+=query_sum(rt<<1|1,mid+1,r,max(xl,mid+1),xr);
    return res;
}
ll query_suf(int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(l==xl&&r==xr){
        return t[rt].suf;
    }
    if(xr<=mid)return query_suf(rt<<1,l,mid,xl,xr);
    else if(xl>mid)return query_suf(rt<<1|1,mid+1,r,xl,xr);
    else return min(query_suf(rt<<1,l,mid,xl,mid)+query_sum(rt<<1|1,mid+1,r,mid+1,xr),
        query_suf(rt<<1|1,mid+1,r,mid+1,xr));
}
ll query_pre(int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(l==xl&&r==xr){
        return t[rt].pre;
    }
    if(xr<=mid)return query_pre(rt<<1,l,mid,xl,xr);
    else if(xl>mid)return query_pre(rt<<1|1,mid+1,r,xl,xr);
    else return min(query_pre(rt<<1|1,mid+1,r,mid+1,xr)+query_sum(rt<<1,l,mid,xl,mid),
        query_pre(rt<<1,l,mid,xl,mid));
}
ll query_mn(int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(l==xl&&xr==r){
        return t[rt].mn;
    }
    ll res=0;
    if(xl<=mid)res=min(res,query_mn(rt<<1,l,mid,xl,min(xr,mid)));
    if(xr>mid)res=min(res,query_mn(rt<<1|1,mid+1,r,max(xl,mid+1),xr));
    if(xl<=mid&&xr>mid)res=min(res,query_suf(rt<<1,l,mid,xl,mid)+query_pre(rt<<1|1,mid+1,r,mid+1,xr));
    return res;
}
void update(int rt,int l,int r,int xp){
    int mid=l+r>>1;
    if(l==r){
        t[rt].pre=t[rt].suf=t[rt].mn=t[rt].sum=a[l];
        return;
    }
    if(xp<=mid)update(rt<<1,l,mid,xp);
    else update(rt<<1|1,mid+1,r,xp);
    push_up(rt);
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            int l,r;ll x;
            scanf("%d%d%lld",&l,&r,&x);
            ll dn=(x-1)/10+1;
            ll cur=0;
            if(l!=1)cur=min(cur,query_mn(1,1,n,1,l-1));
            if(l!=1&&cur<=-x)puts("0");
            else {
                ll temp=a[l];
                a[l]=query_suf(1,1,n,1,l);
                update(1,1,n,l);
                cur=query_mn(1,1,n,l,r);
                ll mn_suf=0;
                if(cur<=dn-x||a[l]-temp<=dn-x){
                    mn_suf=dn-x;            
                }
                else {
                    mn_suf=query_suf(1,1,n,l,r);
                }
                a[l]=temp;
                update(1,1,n,l);
                if(r==n)printf("%lld\n",min(x,mn_suf+x));
                else {
                    if(mn_suf<0){
                        ll temp=a[r+1];
                        a[r+1]+=mn_suf;
                        update(1,1,n,r+1);
                        cur=query_mn(1,1,n,r+1,n);
                        if(cur<=-x)puts("0");
                        else printf("%lld\n",min(x,x+query_suf(1,1,n,r+1,n)));
                        a[r+1]=temp;
                        update(1,1,n,r+1);
                    }
                    else {
                        cur=query_mn(1,1,n,r+1,n);
                        if(cur<=-x)puts("0");
                        else printf("%lld\n",min(x,x+query_suf(1,1,n,r+1,n)));
                    }
                }

            }
        }
        else {
            int idx,x;
            scanf("%d%d",&idx,&x);
            a[idx]=x;
            update(1,1,n,idx);
        }
    }

    return 0;
}
/*
6 6
2 5 -3 8 1 -4 
1 2 5 7 
1 1 3 2
2 2 -1 
1 4 6 2
2 1 -1 
1 1 6 6
*/
/*
4 10
0 1 1 -1 
1 2 4 2 
2 2 -1
1 2 4 2 
1 2 3 2 
2 1 -1 
1 1 4 2 
1 2 4 2 
2 1 -2 
1 1 4 2 
1 2 4 2
*/

K.Three Competitions

如果不考虑数据规模，则这是一个很典型的SCC题目，使用tarjan或者kosarajua进行缩点即可。

注意观察数据，发现对于任意两个人，必定有一个人会直接胜过另一个人，假设把胜负关系用一条有向边表示，那么建立出来的图一定是一个有向完全图。

所以我们这里考虑kosarajau算法，在找下一个点的时候使用线段树优化即可。由于每个点只会考虑两次，每个点被找到时会花费lognlogn的时间，则总时间为nlognnlogn

这里找点时，先以一个比赛的结果为基准，再在另外一个比赛中找排名大于自己的人（第二次dfs时找小于，因为边要反过来）

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
178
179
180
181
182
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=2e5+5;
const ll mod=998244353;
int n,q;
int a[4][maxn],rk[4][maxn];
int vis[maxn];
vector<int>st;
pii t[6][maxn<<2];

void push_up(int sgn,int rt){
    if(t[sgn][rt<<1].first>t[sgn][rt<<1|1].first){
        t[sgn][rt]=t[sgn][rt<<1];
    }
    else t[sgn][rt]=t[sgn][rt<<1|1];
}
void build(int sgn,int rt,int l,int r){
    int mid=l+r>>1;
    if(l==r){
        int fst=sgn/3+1,scd=sgn%3+1;        
        t[sgn][rt].second=rk[fst][l];
        t[sgn][rt].first=a[scd][rk[fst][l]];
        return;
    }
    build(sgn,rt<<1,l,mid);
    build(sgn,rt<<1|1,mid+1,r);
    push_up(sgn,rt);    
}
int query(int sgn,int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(l==xl&&xr==r){
        return t[sgn][rt].first;
    }
    int res=0;
    if(xl<=mid)res=max(res,query(sgn,rt<<1,l,mid,xl,min(xr,mid)));
    if(xr>mid)res=max(res,query(sgn,rt<<1|1,mid+1,r,max(mid+1,xl),xr));
    return res;
}
void update(int sgn,int rt,int l,int r,int xp){
    int mid=l+r>>1;
    if(l==r){
        t[sgn][rt]={0,0};
        return;
    }
    if(xp<=mid)update(sgn,rt<<1,l,mid,xp);
    else update(sgn,rt<<1|1,mid+1,r,xp);
    push_up(sgn,rt);
}
int findfst(int u){
    int sgn=0;
    for(int i=0;i<3;i++){
        sgn=0;
        for(int j=0;j<3;j++){
            if(i==j)continue;
            sgn*=3,sgn+=j;
        }
        int fst=sgn/3+1,scd=sgn%3+1;
        int res=query(sgn,1,1,n,a[fst][u],n);
        if(res>a[scd][u]) return rk[scd][res];
		
    }
    return 0;
}

void invpush_up(int sgn,int rt){
    if(t[sgn][rt<<1].first<t[sgn][rt<<1|1].first){
        t[sgn][rt]=t[sgn][rt<<1];
    }
    else t[sgn][rt]=t[sgn][rt<<1|1];
}
void invbuild(int sgn,int rt,int l,int r){
    int mid=l+r>>1;
    if(l==r){
        int fst=sgn/3+1,scd=sgn%3+1;        
        t[sgn][rt].second=rk[fst][l];
        t[sgn][rt].first=a[scd][rk[fst][l]];
        return;
    }
    invbuild(sgn,rt<<1,l,mid);
    invbuild(sgn,rt<<1|1,mid+1,r);
    invpush_up(sgn,rt);    
}
int invquery(int sgn,int rt,int l,int r,int xl,int xr){
    int mid=l+r>>1;
    if(l==xl&&xr==r){
        return t[sgn][rt].first;
    }
    int res=n+1;
    if(xl<=mid)res=min(res,invquery(sgn,rt<<1,l,mid,xl,min(xr,mid)));
    if(xr>mid)res=min(res,invquery(sgn,rt<<1|1,mid+1,r,max(mid+1,xl),xr));
    return res;
}
void invupdate(int sgn,int rt,int l,int r,int xp){
    int mid=l+r>>1;
    if(l==r){
        t[sgn][rt]={n+1,n+1};
        return;
    }
    if(xp<=mid)invupdate(sgn,rt<<1,l,mid,xp);
    else invupdate(sgn,rt<<1|1,mid+1,r,xp);
    invpush_up(sgn,rt);
}
int invfindfst(int u){
    int sgn=0;
    for(int i=0;i<3;i++){
        sgn=0;
        for(int j=0;j<3;j++){
            if(i==j)continue;
            sgn*=3,sgn+=j;
        }
        int fst=sgn/3+1,scd=sgn%3+1;
        int res=invquery(sgn,1,1,n,1,a[fst][u]);
        if(res<a[scd][u])return rk[scd][res];
    }
    return 0;
}

void kosarajau(int u){
    vis[u]=1;
    update(1,1,1,n,a[1][u]);
    update(2,1,1,n,a[1][u]);
    update(5,1,1,n,a[2][u]);
    int v=0;
    while((v=findfst(u))&&v){
        kosarajau(v);
    }
	st.push_back(u);
}
int tot;
int in[maxn];
void dfs(int u){
    vis[u]=0;
    in[u]=tot;
   	invupdate(1,1,1,n,a[1][u]);
    invupdate(2,1,1,n,a[1][u]);
    invupdate(5,1,1,n,a[2][u]);
    int v=0;
    while((v=invfindfst(u))&&v){
        dfs(v);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            scanf("%d",&a[j][i]);
            rk[j][a[j][i]]=i;
        }
    }
    build(1,1,1,n);
    build(2,1,1,n);
    build(5,1,1,n);
    for(int i=1;i<=n;i++){
        if(vis[i])continue;
        kosarajau(i);
    }
    invbuild(1,1,1,n);
    invbuild(2,1,1,n);
    invbuild(5,1,1,n);
    while(!st.empty()){
        int p=st.back();
        st.pop_back();
        if(!vis[p])continue;
        ++tot;
        dfs(p);
    }

    scanf("%d",&q);
    while(q--){
        int x,y;
        scanf("%d%d",&x,&y);
        int cnt=0;
        for(int i=1;i<=3;i++){
            if(a[i][x]<a[i][y])cnt++;
        }
        if(cnt>=2||in[x]==in[y])puts("YES");
        else puts("NO");
    }
    return 0;
}