2013-2014 Petrozavodsk Winter Training Camp, Moscow SU Trinity Contest 补题记录（7 / 11）

发表于 更新于 分类于 本文字数： 25k 阅读时长 ≈ 23 分钟

2013-2014 ptz Moscow 补题记录，有空待补…

A. MEX-Query

tag

  • 线段树

题意

序列长为 nn ， qq 次询问求区间 mexmex 。
其中 1≤n,q≤1061 \leq n, q \leq 10^6 。

思路

询问离线下来按 rr 排序，开权值树记每个数最后一次出现位置的最小值即可。
复杂度 O(n⋅logn)O(n \cdot logn) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-24 16:25:28
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int N=1e6+5;

struct Seg_Tree{
    int minn[N<<2];
    void change(int x,int l,int r,int pos,int val){
        if(l==r){
            minn[x]=val;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid) change(x<<1,l,mid,pos,val);
        else change(x<<1|1,mid+1,r,pos,val);
        minn[x]=min(minn[x<<1],minn[x<<1|1]);
        return;
    }
    int search(int x,int l,int r,int val){
        if(l==r) return l;
        int mid=l+r>>1;
        if(minn[x<<1]<val) return search(x<<1,l,mid,val);
        else return search(x<<1|1,mid+1,r,val);
    }
}tr;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<int> a(n+5,0);
    for(int i=1;i<=n;i++) cin>>a[i];

    int q;
    cin>>q;
    
    vector<vector<array<int,2>>> qry(n+5);
    for(int i=1,l,r;i<=q;i++){
        cin>>l>>r;
        qry[r].push_back({l,i});
    }

    vector<int> ans(q+5,0);
    for(int r=1;r<=n;r++){
        tr.change(1,0,n,a[r],r);
        for(auto [l,id]:qry[r]) ans[id]=tr.search(1,0,n,l);
    }

    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";

    return true&&false;
}

C. The Palindrome Extraction

tag

  • manacher
  • 后缀自动机

题意

给定长为 nn 的串 ss ，求两段互不相交的子串 B,DB, D ，使得 B+DB + D 为回文串且最大化 B+DB + D 的长度。
其中 1≤n≤1051 \leq n \leq 10^5 。

思路

不妨假设 ∣B∣>∣D∣|B| > |D| ，枚举回文中心，可以反证该回文中心的回文串取到的长度越长越好，回文串长度可以二分或者 manachermanacher 跑出来。
回文中心一定在 BB 上，假设该回文串所在区间为 [l,r][l, r] ，则等价于需要找最长的 lenlen 满足存在 s[l−len,l−1]=rev(s[x,x+len−1]) (r+1≤x≤n−len+1)s[l - len, l - 1] = rev(s[x, x + len - 1])\ (r + 1 \leq x \leq n - len + 1) 。
显然 lenlen 是可以二分的，只需要考虑如何 checkcheck 。
定义 t=s+rev(s)t = s + rev(s) ，建出 tt 的 samsam 。对于给定的 lenlen ，可以找到 s[l−len,l−1]s[l - len, l - 1] 对应子串在 linklink 树上的对应节点，这一步可以先找到 s[1,l−1]s[1, l - 1] 的对应节点再往父节点跳。接下来只需要查找该节点的 endposendpos 集合中存不存在符合条件的位置 xx ，线段树合并维护一下 endposendpos 集合即可。
复杂度 O(n⋅log2n)O(n \cdot log^2n) 。

代码

常数巨大…

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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
/*
    Author: Cupids_Bow
    Time: 2022-10-25 19:52:46
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int mod=1e9+7;
const int base=114514;
const int N=2e5+5;
const int M=26;

int n;
struct Seg_Tree{
    int tot;
    int rt[N*2];
    int lc[N<<5];
    int rc[N<<5];
    int endpos[N<<5];
    void clear(){
        tot=0;
        memset(rt,0,sizeof(rt));
    }
    Seg_Tree(){
        clear();
    }
    int addnode(){
        tot++;
        lc[tot]=rc[tot]=endpos[tot]=0;
        return tot;
    }
    void cpy(int x,int y){
        lc[x]=lc[y];
        rc[x]=rc[y];
        endpos[x]=endpos[y];
    }
    void pushup(int x){
        if(endpos[lc[x]]) endpos[x]=endpos[lc[x]];
        if(endpos[rc[x]]) endpos[x]=endpos[rc[x]];
    }
    void insert(int &x,int l,int r,int pos){
        if(!x) x=addnode();
        if(l==r){
            endpos[x]=l;
            return;
        }
        int mid=l+r>>1;
        if(pos<=mid) insert(lc[x],l,mid,pos);
        else insert(rc[x],mid+1,r,pos);
        pushup(x);
        return;
    }
    void merge(int &x,int &y,int l,int r){
        if(!y) return;
        if(!x){
            x=y;
            return;
        }
        addnode();
        cpy(tot,x);
        x=tot;
        if(l==r){
            endpos[x]=endpos[y];
            return;
        }
        int mid=l+r>>1;
        merge(lc[x],lc[y],l,mid);
        merge(rc[x],rc[y],mid+1,r);
        pushup(x);
        return;
    }
    int search(int x,int l,int r,int ql,int qr){
        if(!x||ql>qr) return 0;
        if(l>=ql&&r<=qr) return endpos[x];
        int mid=l+r>>1;
        int res=0;
        if(mid>=ql) res=search(lc[x],l,mid,ql,qr);
        if(res) return res;
        if(mid+1<=qr) res=search(rc[x],mid+1,r,ql,qr);
        return res;
    }
}tr;
struct SAM{
    int tot;
    int nex[N*2][M];
    int len[N*2];
    int link[N*2];
    int cnt[N*2];
    vector<int> e[N*2];
    array<int,19> f[N*2];
    int lst;
    void clear(){
        tot=0;
        len[0]=cnt[0]=lst=0;
        link[0]=-1;
        e[0].clear();
        memset(nex[0],0,sizeof(nex[0]));
    }
    SAM(){
        clear();
    }
    int addnode(){
        tot++;
        len[tot]=cnt[tot]=0;
        link[tot]=-1;
        e[tot].clear();
        memset(nex[tot],0,sizeof(nex[tot]));
        return tot;
    }
    void cpy(int x,int y){
        for(int i=0;i<M;i++) nex[x][i]=nex[y][i];
        len[x]=len[y];
        link[x]=link[y];
        cnt[x]=0;
    }
    int extend(char c,int ind){
        int w=c-'a';
        int u=addnode();
        len[u]=len[lst]+1;
        int p=lst;
        while(p!=-1&&!nex[p][w]){
            nex[p][w]=u;
            p=link[p];
        }
        if(p==-1) link[u]=0;
        else{
            int q=nex[p][w];
            if(len[p]+1==len[q]) link[u]=q;
            else{
                int clone=addnode();
                cpy(clone,q);
                len[clone]=len[p]+1;
                while(p!=-1&&nex[p][w]==q){
                    nex[p][w]=clone;
                    p=link[p];
                }
                link[q]=link[u]=clone;
            }
        }
        lst=u;
        cnt[u]++;
        if(ind>=n+1) tr.insert(tr.rt[lst],n+1,n*2,ind);
        return lst;
    }
    void add_edge(){
        for(int i=1;i<=tot;i++) e[link[i]].push_back(i);
    }
    void dfs(int x,int fa){
        f[x][0]=fa;
        for(int i=1;i<19;i++) f[x][i]=f[f[x][i-1]][i-1];
        for(auto v:e[x]){
            dfs(v,x);
            tr.merge(tr.rt[x],tr.rt[v],n+1,n*2);
        }
    }
    int get(int x,int l){
        for(int i=18;i>=0;i--) if(l<=len[link[f[x][i]]]) x=f[x][i];
        while(!(len[f[x][0]]<l&&l<=len[x])) x=f[x][0];
        return x;
    }
}sam;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    vector<int> pow_(N,0);
    pow_[0]=1;
    for(int i=1;i<N;i++) pow_[i]=1ll*pow_[i-1]*base%mod;

    string s;
    cin>>s;
    n=s.size();

    auto calc=[&](string s){
        array<int,5> res={0,-1,-1,-1,-1};

        vector<int> pos(n*2+5,0);
        sam.clear();
        tr.clear();
        for(int i=1;i<=n;i++) pos[i]=sam.extend(s[i-1],i);
        for(int i=n+1;i<=n*2;i++) pos[i]=sam.extend(s[n*2-i],i);
        sam.add_edge();
        sam.dfs(0,0);

        vector<int> has(n*2+5,0);
        for(int i=1;i<=n;i++) has[i]=(1ll*has[i-1]*base%mod+s[i-1])%mod;
        for(int i=n+1;i<=n*2;i++) has[i]=(1ll*has[i-1]*base%mod+s[n*2-i])%mod;

        auto calc=[&](int l,int r){
            return (has[r]+mod-1ll*has[l-1]*pow_[r-l+1]%mod)%mod;
        };

        for(int i=1;i<=n;i++){
            int l=1,r=min(i,n-i+1),len1=1;
            while(l<=r){
                int mid=l+r>>1;
                if(calc(i-mid+1,i)==calc(n*2-i-mid+2,n*2-i+1)) len1=mid,l=mid+1;
                else r=mid-1;
            }

            l=1,r=i-len1;
            int len2=0,endpos=0;
            while(l<=r){
                int mid=l+r>>1;
                int now=sam.get(pos[i-len1],mid);
                int ep=tr.search(tr.rt[now],n+1,n*2,n+mid,n*2-i-len1+1);
                if(ep==0) r=mid-1;
                else len2=mid,endpos=ep,l=mid+1;
            }
            if(len1*2-1+len2*2>res[0]){
                res[0]=len1*2-1+len2*2;
                if(len1+len2>0) res[1]=i-len1-len2+1,res[2]=i+len1-1;
                else res[1]=res[2]=-1;
                if(len2>0) res[3]=n*2-endpos+1,res[4]=n*2-endpos+len2;
                else res[3]=res[4]=-1;
            }
        }

        for(int i=1;i<n;i++){
            int l=0,r=min(i,n-i),len1=0;
            while(l<=r){
                int mid=l+r>>1;
                if(calc(i-mid+1,i)==calc(n*2-i-mid+1,n*2-i)) len1=mid,l=mid+1;
                else r=mid-1;
            }

            l=1,r=i-len1;
            int len2=0,endpos=0;
            while(l<=r){
                int mid=l+r>>1;
                int now=sam.get(pos[i-len1],mid);
                int ep=tr.search(tr.rt[now],n+1,n*2,n+mid,n*2-i-len1);
                if(ep==0) r=mid-1;
                else len2=mid,endpos=ep,l=mid+1;
            }
            if(len1*2+len2*2>res[0]){
                res[0]=len1*2+len2*2;
                if(len1+len2>0) res[1]=i-len1-len2+1,res[2]=i+len1;
                else res[1]=res[2]=-1;
                if(len2>0) res[3]=n*2-endpos+1,res[4]=n*2-endpos+len2;
                else res[3]=res[4]=-1;
            }
        }

        return res;
    };

    array<int,5> res1=calc(s);

    reverse(s.begin(),s.end());

    array<int,5> res2=calc(s);
    array<int,5> res3={res2[0],-1,-1,-1,-1};
    if(res2[1]!=-1){
        res3[3]=n-res2[2]+1;
        res3[4]=n-res2[1]+1;
    }
    if(res2[3]!=-1){
        res3[1]=n-res2[4]+1;
        res3[2]=n-res2[3]+1;
    }

    if(res1[0]>=res3[0]) cout<<res1[0]<<"\n"<<res1[1]<<" "<<res1[2]<<"\n"<<res1[3]<<" "<<res1[4];
    else cout<<res3[0]<<"\n"<<res3[1]<<" "<<res3[2]<<"\n"<<res3[3]<<" "<<res3[4];

    return true&&false;
}

D. Short Enough Task

tag

  • 数学

题意

串长为 nn 字符集大小为 kk ，求期望回文子串个数。
其中 1≤n,k≤1091 \leq n, k \leq 10^9 。

思路

枚举一下长度段贡献即可，精度为 10−610^{-6} ，长度稍微枚举一点即可，特判 n=1n = 1 。
复杂度 O(?)O(?) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-24 16:11:42
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n,k;
    cin>>n>>k;

    if(k==1){
        cout<<1ll*n*(n+1)/2;
        return true&&false;
    }

    double ans=0;
    for(int len=1;len<=min(n,514);len++){
        ans+=pow(1.0/k,len/2)*(n-len+1);
    }
    cout<<fixed<<setprecision(18)<<ans;

    return true&&false;
}

E. Another Short Problem

tag

  • 期望
  • 计算几何

题意

给定 nn 个点，每个点有 pp 的概率被选中，求选中的点构成的凸包的期望顶点数。
其中 1≤n≤501 \leq n \leq 50 。

思路

对于多面体有欧拉公式 F+V−E′=2F + V - E' = 2 ， FF 表示面数， E′E' 表示棱数， VV 表示顶点数，在期望条件下也成立。
所以有 E(F)+E(V)−E(E′)=2E(F) + E(V) - E(E') = 2 即 E(V)=2+E(E′)−E(F)E(V) = 2 + E(E') - E(F) 。
期望面数可以通过枚举三个点表示的平面求得。由于不存在四点共面，所以所有面均为三角形，可以得到 E(E′)=3⋅E(F)2E(E') = \frac{3 \cdot E(F)}{2} ，所以 E(V)=2+E(F)2E(V) = 2 + \frac{E(F)}{2} 。
但上述公式是对于凸多面体而言，对于不能构成凸多面体的情况（如点数为 0,1,20, 1, 2 时）是没有被计算到的。
具体的：

  • 点数 V=0V = 0 时，此时有 2+E′−F=02 + E' - F = 0 ，而我们计算时按照 E′=F=0E' = F = 0 ， 2+E′−F=22 + E' - F = 2 答案多算了 22 。
  • 点数 V=1V = 1 时，此时有 2+E′−F=12 + E' - F = 1 ，而我们计算时按照 E′=F=0E' = F = 0 ， 2+E′−F=22 + E' - F = 2 答案多算了 11 。
  • 点数 V=2V = 2 时，此时有 2+E′−F=22 + E' - F = 2 ，而我们计算时按照 E′=F=0E' = F = 0 ， 2+E′−F=22 + E' - F = 2 答案多算了 00 。

把多计算的减去就可以了。
复杂度 O(n4)O(n^4) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-24 19:40:31
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const double eps=1e-8;
const double inf=1e20;
const double pi=acos(-1.0);
const int maxp=50+5;

int sgn(double x){
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}

inline double sqr(double x){return x*x;}

struct Point3{
    double x,y,z;
    Point3(double _x=0,double _y=0,double _z=0){
        x=_x;
        y=_y;
        z=_z;
    }
    void input(){
        cin>>x>>y>>z;
    }
    void output(){
        cout<<x<<" "<<y<<" "<<z<<"\n";
    }
    bool operator == (const Point3 &b)const{
        return sgn(x-b.x)==0&&sgn(y-b.y)==0&&sgn(z-b.z)==0;
    }
    bool operator < (const Point3 &b)const{
        return sgn(x-b.x)==0?(sgn(y-b.y)==0?sgn(z-b.z)<0:y<b.y):x<b.x;
    }
    double len(){
        return sqrt(x*x+y*y+z*z);
    }
    double len2(){
        return x*x+y*y+z*z;
    }
    double distance(const Point3 &b)const{
        return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y)+(z-b.z)*(z-b.z));
    }
    Point3 operator - (const Point3 &b)const{
        return Point3(x-b.x,y-b.y,z-b.z);
    }
    Point3 operator + (const Point3 &b)const{
        return Point3(x+b.x,y+b.y,z+b.z);
    }
    Point3 operator * (const double &k)const{
        return Point3(x*k,y*k,z*k);
    }
    Point3 operator / (const double &k)const{
        return Point3(x/k,y/k,z/k);
    }
    double operator * (const Point3 &b)const{
        return x*b.x+y*b.y+z*b.z;
    }
    Point3 operator ^ (const Point3 &b)const{
        return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);
    }
    double rad(Point3 a,Point3 b){
        Point3 p=(*this);
        return acos(((a-p)*(b-p))/(a.distance(p)*b.distance(p)));
    }
    Point3 trunc(double r){
        double l=len();
        if(!sgn(l)) return *this;
        r/=l;
        return Point3(x*r,y*r,z*r);
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<double> p(n,0);
    vector<Point3> p3(n,0);
    for(int i=0,x,y,z;i<n;i++) cin>>p[i]>>p3[i].x>>p3[i].y>>p3[i].z;

    double ans=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            for(int k=j+1;k<n;k++){
                Point3 s=(p3[j]-p3[i])^(p3[k]-p3[i]);
                double res1=1,res2=1;
                for(int l=0;l<n;l++) if(l!=i&&l!=j&&l!=k){
                    double v=(p3[i]-p3[l])*s;
                    if(v>0) res1*=(1-p[l]);
                    else res2*=(1-p[l]);
                }
                ans+=p[i]*p[j]*p[k]*(res1+res2);
            }
    ans/=2;

    for(int i=0;i<n;i++){
        double res=p[i];
        for(int j=0;j<n;j++) if(j!=i) res*=1-p[j];
        ans-=res;
    }

    double res=1;
    for(int i=0;i<n;i++) res*=1-p[i];
    ans-=2*res;

    ans+=2;

    cout<<fixed<<setprecision(8)<<ans;

    return true&&false;
}

F. Just Another Sequence Problem

tag

  • dp
  • 斜率优化

题意

将给定长为 nn 的序列 aa 分为 kk 段，第 ii 段是 si=∑ajs_i = \sum a_j ，贡献是 ∑i=1k−1si⋅si+1\sum\limits_{i = 1}^{k - 1} s_i \cdot s_{i + 1} ，最大化贡献。
其中 1≤n≤2000,−1000≤ai≤10001 \leq n \leq 2000, -1000 \leq a_i \leq 1000 。

思路

有朴素的 O(n3)O(n^3) 的 dpdp :

  • dp[i][j]dp[i][j] 表示计算了前i个，最后一段为 [j,i][j, i] 时的最大贡献。
  • 转移为 dp[i][j]=max(dp[j−1][k]+(sum[j−1]−sum[k])⋅(sum[i]−sum[j−1])) (1≤k≤j−1)dp[i][j] = max(dp[j - 1][k] + (sum[j - 1] - sum[k]) \cdot (sum[i] - sum[j - 1]))\ (1 \leq k \leq j - 1) 。
  • 边界为 dp[i][1]=0 (1≤i≤n)dp[i][1] = 0\ (1 \leq i \leq n) 。

将 sumsum 乘进发现可以斜率优化，枚举 jj 构造 kk 的凸包转移 ii 即可。 aia_i 可能小于 00 ，所以横坐标不一定递增，需要先排序。
复杂度 O(n2⋅logn)O(n^2 \cdot logn) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-10-24 18:29:37
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const i64 INF=0x3f3f3f3f3f3f3f3f;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<i64> sum(n+5,0);
    for(int i=1;i<=n;i++) cin>>sum[i];

    for(int i=1;i<=n;i++) sum[i]+=sum[i-1];

    vector<vector<i64>> dp(n+5,vector<i64>(n+5,-INF));
    vector<i64> x(n+5,0),y(n+5,0),p(n+5,0);
    for(int i=1;i<=n;i++) dp[i][1]=0;
    for(int j=2;j<=n;j++){
        vector<int> convex;
        for(int k=1;k<=j-1;k++){
            x[k]=sum[k-1];
            y[k]=dp[j-1][k];
            p[k]=k;
        }
        sort(p.begin()+1,p.begin()+j,[&](const int &a,const int &b){
            return x[a]<x[b];
        });

        for(int k=1;k<=j-1;k++){
            auto check=[&](int a,int b,int c){
                i64 xa=x[a],ya=y[a];
                i64 xb=x[b],yb=y[b];
                i64 xc=x[c],yc=y[c];
                return (yc-ya)*(xb-xa)>=(yb-ya)*(xc-xa);
            };

            int len=convex.size();
            while(len>=2&&check(convex[len-2],convex[len-1],p[k])){
                convex.pop_back();
                len--;
            }
            convex.push_back(p[k]);
        }

        for(int i=j;i<=n;i++) p[i]=i;
        sort(p.begin()+j,p.begin()+1+n,[&](const int &a,const int &b){
            return sum[a]>sum[b];
        });

        int pos=0;
        for(int i=j;i<=n;i++){
            auto check=[&](int a,int b,i64 slope){
                i64 xa=sum[a-1],ya=dp[j-1][a];
                i64 xb=sum[b-1],yb=dp[j-1][b];
                return (yb-ya)>=(xb-xa)*slope;
            };

            while(pos+1<convex.size()&&check(convex[pos],convex[pos+1],sum[p[i]]-sum[j-1])) pos++;
            dp[p[i]][j]=dp[j-1][convex[pos]]+(sum[p[i]]-sum[j-1])*(sum[j-1]-sum[convex[pos]-1]);
        }
    }

    i64 ans=dp[n][1];
    for(int i=2;i<=n;i++) ans=max(ans,dp[n][i]);

    cout<<ans;

    return true&&false;
}

J. Dividing Area

tag

  • 计算几何
  • 并查集

题意

给定二维平面 nn 个点。
qq 次操作，每次操作如下：

  • 选两个点连一条线段，保证所有线段除了端点外不会相交。
  • 询问有向线段 abab 左侧平面的面积，无限输出 −1-1 。

其中 1≤n≤2⋅105,1≤q≤1061 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 10^6 。

思路

若将所有操作反过来，则加边的操作变为断边，即为合并两个相邻的平面。
考虑如何计算一个凸包的面积： area=∑i=0ncross(p[i],p[(i+1)%n])area = \sum\limits_{i = 0}^{n} cross(p[i], p[(i+1)\%n]) ，可以看成每条边的贡献之和。
类似的，对将要加入的线段 uvuv ，将其分为两条有向线段 uv,vuuv, vu ，分别给其左右平面编号。则每条线段对其左侧平面的贡献可以叉积求得。
一个平面的总面积即为所有包围它的线段的贡献和。
所有询问线段可以分为三种情况：

  • 询问线段左侧为一个凸多边形，则线段的贡献和即为所求面积。

  • 询问线段左侧为一个 CC 字，则线段的正反面贡献相互抵消，贡献和为 00 ，面积为无限。

  • 询问线段左侧为一个 CC 字上附着若干个多边形， CC 字部分的贡献相互抵消结果应为 00 ，另外减去多边形的面积，最后贡献和为负数，面积为无限。

则可以得到，平面的面积为无限当且仅当它的贡献和小于等于 00 。
则可以将给定询问倒过来处理，每次加边操作相当于合并两个相邻平面，并查集维护平面贡献即可。初始化将所有共端点的线段的平面合并即可。
复杂度 O(q⋅logq)O(q \cdot logq) 。

代码

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
/*
    Author: Cupids_Bow
    Time: 2022-11-02 20:17:11
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int maxp=2e5+5;
const int maxn=1e6+5;

int sgn(i64 x){
    if(x==0) return 0;
    if(x<0) return -1;
    else return 1;
}

inline i64 sqr(i64 x){return x*x;}

struct Point{
    i64 x,y;
    Point(i64 _x=0,i64 _y=0){
        x=_x;
        y=_y;
    }
    void input(){
        cin>>x>>y;
    }
    void output(){
        cout<<x<<" "<<y<<"\n";
    }
    bool operator == (Point b)const{
        return sgn(x-b.x)==0&&sgn(y-b.y)==0;
    }
    bool operator < (Point b)const{
        return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;
    }
    Point operator - (const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    i64 operator ^ (const Point &b)const{
        return x*b.y-y*b.x;
    }
    i64 operator * (const Point &b)const{
        return x*b.x+y*b.y;
    }
    Point operator + (const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator * (const i64 &k)const{
        return Point(x*k,y*k);
    }
};
struct DSU{
    int fa[maxn*2];
    i64 area[maxn*2];
    int get(int x){
        if(fa[x]==x) return x;
        return fa[x]=get(fa[x]);
    }
    void merge(int x,int y){
        int r1=get(x),
            r2=get(y);
        if(r1==r2) return;
        fa[r1]=r2;
        area[r2]+=area[r1];
        return;
    }
    i64 getarea(int x){
        x=get(x);
        if(area[x]<=0) return -1;
        else return area[x];
    }
}dsu;
vector<int> e[maxp];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    vector<Point> p(n);
    for(int i=0;i<n;i++) p[i].input();

    int q;
    cin>>q;

    vector<array<int,3>> qry(q,{0,0,0});
    map<array<int,2>,int> mp;
    int tot=0;
    for(auto &[op,u,v]:qry){
        cin>>op>>u>>v;
        if(op==1){
            mp[{u,v}]=tot;
            dsu.area[tot]=p[u]^p[v];
            tot++;
            mp[{v,u}]=tot;
            dsu.area[tot]=p[v]^p[u];
            tot++;

            e[u].push_back(v);
            e[v].push_back(u);
        }
    }
    for(int i=0;i<tot;i++) dsu.fa[i]=i;

    for(int i=0;i<n;i++){
        sort(e[i].begin(),e[i].end(),[&](const int &u,const int &v){
            Point p1=p[u]-p[i];
            Point p2=p[v]-p[i];
            return atan2l(p1.y,p1.x)>atan2l(p2.y,p2.x);
        });
        int m=e[i].size();
        for(int j=0;j<m;j++) dsu.merge(mp[{e[i][j],i}],mp[{i,e[i][(j+1)%m]}]);
    }

    reverse(qry.begin(),qry.end());
    vector<i64> ans;
    for(auto [op,u,v]:qry){
        if(op==1) dsu.merge(mp[{u,v}],mp[{v,u}]);
        else ans.push_back(dsu.getarea(mp[{u,v}]));
    }

    reverse(ans.begin(),ans.end());
    for(auto x:ans) cout<<x<<"\n";

    return true&&false;
}

K. Tree Problem

tag

  • 树链剖分
  • 线段树

题意

给定 nn 个节点的树， qq 次操作，每次操作如下：

  • 计算路径 abab 上有多少条边被标记。
  • 将路径 abab 上的边取消标记，并将直接连接在路径 abab 上的所有边记上标记。

初始所有边均被标记。
其中 1≤n≤2⋅105,1≤q≤3⋅1051 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 3 \cdot 10^5 。

思路

固定 11 为树根，考虑两种映射边的方式，一种是将边映射到它连接的儿子上，即为方案 11 ，一种是映射到它连接的父节点上，即为方案 22 。
考虑树剖，剖完之后用两棵线段树分别维护方案 1,21, 2 ，树 11 维护所有重边，树 22 维护所有轻边。
对于修改链 abab 的操作，直接在链上的边可以直接按方案 11 修改它的子节点，对于连接在路径上的边，这些边是所有链上节点连向的子节点的边并上 abab 的 lcalca 连向父节点的边，前者可以按方案 22 修改对应节点，后者直接特判，在修改前者时会涉及 loglog 条重边，对于这些边也按方案 11 修改即可。
对于查询操作，树剖之后相当于查询 loglog 条重链和 loglog 条轻边，对于重链直接按方案 11 查询，对于轻边，则需要比较方案 1,21, 2 的结果，这里再记录一个修改操作的时间戳即可。
复杂度 O(n⋅log2n)O(n \cdot log^2n) 。

代码

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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
/*
    Author: Cupids_Bow
    Time: 2022-11-03 20:23:13
*/
#include<bits/stdc++.h>
using namespace std;

using i64=long long;

const int N=2e5+5;

struct Seg_Tree{
    int val[N<<2];
    int clk[N<<2];
    array<int,2> lz[N<<2];
    void pushup(int x){
        val[x]=val[x<<1]+val[x<<1|1];
        clk[x]=max(clk[x<<1],clk[x<<1|1]);
    }
    void build(int x,int l,int r,int clock){
        clk[x]=clock;
        lz[x]={-1,-1};
        if(l==r){
            val[x]=1;
            return;
        }
        int mid=l+r>>1;
        build(x<<1,l,mid,clock);
        build(x<<1|1,mid+1,r,clock);
        pushup(x);
        return;
    }
    void pushdown(int x){
        if(lz[x][0]!=-1){
            auto [k,clock]=lz[x];
            if(clock>=clk[x<<1]){
                val[x<<1]=k;
                clk[x<<1]=clock;
                lz[x<<1]=lz[x];
            }
            if(clock>=clk[x<<1|1]){
                val[x<<1|1]=k;
                clk[x<<1|1]=clock;
                lz[x<<1|1]=lz[x];
            }
            lz[x]={-1,-1};
        }
        return;
    }
    void change(int x,int l,int r,int ql,int qr,array<int,2> arr){
        if(ql>qr) return;
        if(l>=ql&&r<=qr){
            auto [k,clock]=arr;
            if(clock<clk[x]) return;
            val[x]=k;
            clk[x]=clock;
            lz[x]=arr;
            return;
        }
        pushdown(x);
        int mid=l+r>>1;
        if(mid>=ql) change(x<<1,l,mid,ql,qr,arr);
        if(mid+1<=qr) change(x<<1|1,mid+1,r,ql,qr,arr);
        pushup(x);
        return;
    }
    int search(int x,int l,int r,int ql,int qr){
        if(ql>qr) return 0;
        if(l>=ql&&r<=qr) return val[x];
        pushdown(x);
        int res=0;
        int mid=l+r>>1;
        if(mid>=ql) res+=search(x<<1,l,mid,ql,qr);
        if(mid+1<=qr) res+=search(x<<1|1,mid+1,r,ql,qr);
        return res;
    }
    array<int,2> search(int x,int l,int r,int pos){
        if(l==r) return {val[x],clk[x]};
        pushdown(x);
        int mid=l+r>>1;
        if(pos<=mid) return search(x<<1,l,mid,pos);
        else return search(x<<1|1,mid+1,r,pos);
    }
}tr[2];
namespace TCD{
    const int N=::N;
    vector<int> e[N];
    int rt,dfn0,clk;
    int sz[N],fa[N],dep[N];
    int dfn[N],son[N],top[N];
    void init(int n,int _rt){
        rt=_rt;
        dfn0=clk=0;
        for(int i=0;i<=n;i++){
            sz[i]=1;
            fa[i]=dfn[i]=top[i]=dep[i]=0;
            son[i]=0;
            e[i].clear();
        }
        sz[0]=0;
    }
    void add(int x,int y){
        e[x].push_back(y);
        e[y].push_back(x);
    }
    void getson(int x,int f){
        fa[x]=f;
        for(auto v:e[x]){
            if(v==f) continue;
            dep[v]=dep[x]+1;
            getson(v,x);
            sz[x]+=sz[v];
            if(sz[v]>sz[son[x]]) son[x]=v;
        }
    }
    void dfs(int x,int f,int tp){
        dfn[x]=++dfn0;
        top[x]=tp;
        if(son[x]) dfs(son[x],x,tp);
        for(auto v:e[x]){
            if(v==f||v==son[x]) continue;
            dfs(v,x,v);
        }
    }
    void divide(){
        getson(rt,0);
        dfs(rt,0,rt);
        clk++;
        tr[0].build(1,1,dfn0,clk);
    }
    int get_lca(int x,int y){
        while(top[x]!=top[y]){
            if(dep[top[x]]>dep[top[y]]) swap(x,y);
            y=fa[top[y]];
        }
        if(dep[x]>dep[y]) swap(x,y);
        return x;
    }
    void change(int x,int y){
        int lca=get_lca(x,y);
        clk+=2;
        if(lca!=x){
            while(top[x]!=top[lca]){
                tr[0].change(1,1,dfn0,dfn[top[x]],dfn[x],{0,clk});
                if(son[x]) tr[0].change(1,1,dfn0,dfn[son[x]],dfn[son[x]],{1,clk-1});
                tr[1].change(1,1,dfn0,dfn[top[x]],dfn[x],{1,clk-1});
                x=fa[top[x]];
            }
            if(x!=lca) tr[0].change(1,1,dfn0,dfn[son[lca]],dfn[x],{0,clk});
            if(son[x]) tr[0].change(1,1,dfn0,dfn[son[x]],dfn[son[x]],{1,clk-1});
            tr[1].change(1,1,dfn0,dfn[lca],dfn[x],{1,clk-1});
        }
        if(lca!=y){
            while(top[y]!=top[lca]){
                tr[0].change(1,1,dfn0,dfn[top[y]],dfn[y],{0,clk});
                if(son[y]) tr[0].change(1,1,dfn0,dfn[son[y]],dfn[son[y]],{1,clk-1});
                tr[1].change(1,1,dfn0,dfn[top[y]],dfn[y],{1,clk-1});
                y=fa[top[y]];
            }
            if(y!=lca) tr[0].change(1,1,dfn0,dfn[son[lca]],dfn[y],{0,clk});
            if(son[y]) tr[0].change(1,1,dfn0,dfn[son[y]],dfn[son[y]],{1,clk-1});
            tr[1].change(1,1,dfn0,dfn[lca],dfn[y],{1,clk-1});
        }
        if(fa[lca]) tr[0].change(1,1,dfn0,dfn[lca],dfn[lca],{1,clk});
        if(x==y){
            if(son[x]) tr[0].change(1,1,dfn0,dfn[son[x]],dfn[son[x]],{1,clk-1});
            tr[1].change(1,1,dfn0,dfn[x],dfn[x],{1,clk-1});
        }
    }
    int search(int x,int y){
        int res=0,lca=get_lca(x,y);
        if(lca!=x){
            while(top[x]!=top[lca]){
                if(top[x]!=x) res+=tr[0].search(1,1,dfn0,dfn[son[top[x]]],dfn[x]);
                auto arr0=tr[0].search(1,1,dfn0,dfn[top[x]]);
                auto arr1=tr[1].search(1,1,dfn0,dfn[fa[top[x]]]);
                res+=(arr0[1]>=arr1[1]?arr0[0]:arr1[0]);
                x=fa[top[x]];
            }
            if(x!=lca) res+=tr[0].search(1,1,dfn0,dfn[son[lca]],dfn[x]);
        }
        if(lca!=y){
            while(top[y]!=top[lca]){
                if(top[y]!=y) res+=tr[0].search(1,1,dfn0,dfn[son[top[y]]],dfn[y]);
                auto arr0=tr[0].search(1,1,dfn0,dfn[top[y]]);
                auto arr1=tr[1].search(1,1,dfn0,dfn[fa[top[y]]]);
                res+=(arr0[1]>=arr1[1]?arr0[0]:arr1[0]);
                y=fa[top[y]];
            }
            if(y!=lca) res+=tr[0].search(1,1,dfn0,dfn[son[lca]],dfn[y]);
        }
        return res;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    int n;
    cin>>n;

    TCD::init(n,1);
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        TCD::add(x,y);
    }
    TCD::divide();

    int q;
    cin>>q;

    while(q--){
        int op;
        cin>>op;

        if(op==0){
            int x,y;
            cin>>x>>y;

            cout<<TCD::search(x,y)<<"\n";
        }
        else{
            int x,y;
            cin>>x>>y;

            TCD::change(x,y);
        }
    }

    return true&&false;
}