NOI 记

NOI 记

加油 NOI 。

P5755 [NOI2000] 单词查找树

【模板】字典树。

题目链接： [NOI2000] 单词查找树 。

题目描述：

在进行文法分析的时候，通常需要检测一个单词是否在我们的单词列表里。为了提高查找和定位的速度，通常都要画出与单词列表所对应的单词查找树，其特点如下：

  • 根节点不包含字母，除根节点外每一个节点都仅包含一个大写英文字母；
  • 从根节点到某一节点，路径上经过的字母依次连起来所构成的字母序列，称为该节点对应的单词。单词列表中的每个词，都是该单词查找树某个节点所对应的单词；
  • 在满足上述条件下，该单词查找树的节点数最少。

对一个确定的单词列表，请统计对应的单词查找树的节点数（包括根节点）。

这个题有意思的点是，它直接把字典树是啥告诉你了，所以这也是一个简单模拟题。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
string s;
int nxt[N][26];
int cnt=1; 
void add(string t){
	int len=t.size()-1;
	int fa=1;
	for(int i=0;i<=len;i++){
		char c=t[i];
		if(nxt[fa][c-'a']==0){
			cnt++;
			nxt[fa][c-'a']=cnt;
		}
		fa=nxt[fa][c-'a'];
	}
}
int main(){
	while(cin>>s){
		add(s);
	}
	cout<<cnt;
	return 0;
}

P5691 [NOI2001] 方程的解数

【模板】折半搜索。

题目链接： [NOI2001] 方程的解数 。

题目描述：

已知一个 nn 元高次方程：

∑i=1nkixipi=0\sum\limits_{i=1}^n k_ix_i^{p_i} = 0

其中：x1,x2,…,xnx_1, x_2, \dots ,x_n 是未知数，k1,k2,…,knk_1,k_2, \dots ,k_n 是系数，p1,p2,…pnp_1,p_2,…p_n 是指数。且方程中的所有数均为整数。

假设未知数 xi∈[1,m] (i∈[1,n])x_i \in [1,m] \space ( i \in [1,n])，求这个方程的整数解的个数。

对于 100%100\% 的数据，1≤n≤61\le n \le 6，1≤m≤1501\le m \le 150，且

∑i=1n∣kimpi∣<231\sum\limits_{i=1}^n |k_im^{p_i}| < 2^{31}

答案不超过 231−12^{31}-1，pi∈N∗∩[0,231)p_i \in \mathbb N^*\cap[0,2^{31})。

经典套路。暴力是 O(n6)O(n^6) 。折半搜索，记录一半，搜索一半，复杂度 O(n3)O(n^3) ，足以通过。

代码：

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=10;
int n,k[N],p[N],m;
int kpow(int a,int b){
    int t=1;
    while(b){
        if(b&1)t=t*a;
        a=a*a;
        b>>=1;
    }
    return t;
}
unordered_map<int,int>mp;
int ans=0;
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>k[i]>>p[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            for(int l=1;l<=m;l++){
                mp[k[1]*kpow(i,p[1])+k[2]*kpow(j,p[2])+k[3]*kpow(l,p[3])]++;
            }
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            for(int l=1;l<=m;l++){
                ans+=mp[-k[4]*kpow(i,p[4])-k[5]*kpow(j,p[5])-k[6]*kpow(l,p[6])];
            }
        }
    }
    cout<<ans/kpow(m,6-n);
    return 0;
}

P5468 [NOI2019] 回家路线

【模板】斜率优化。

题目链接： [NOI2019] 回家路线 。

加强版题目链接： [NOI2019] 回家路线 加强版 。

题目描述：

猫国的铁路系统中有 nn 个站点，从 1−n1 - n 编号。小猫准备从 11 号站点出发，乘坐列车回到猫窝所在的 nn 号站点。它查询了能够乘坐的列车，这些列车共 mm 班，从 1−m1 - m 编号。小猫将在 00 时刻到达 11 号站点。对于 ii 号列车，它将在时刻 pip_i 从站点 xix_i 出发，在时刻 qiq_i 直达站点 yiy_i，小猫只能在时刻 pip_i 上 ii 号列车，也只能在时刻 qiq_i 下 ii 号列车。小猫可以通过多次换乘到达 nn 号站点。一次换乘是指对于两班列车，假设分别为 uu 号与 vv 号列车，若 yu=xvy_u = x_v 并且 qu≤pvq_u \leq p_v，那么小猫可以乘坐完 uu 号列车后在 yuy_u 号站点等待 pv−qup_v - q_u 个时刻，并在时刻 pvp_v 乘坐 vv 号列车。

小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。

  • 小猫在站点等待时将增加烦躁值，对于一次 t(t≥0)t (t \geq 0) 个时刻的等待，烦躁值将增加 At2+Bt+CAt^2 + Bt + C，其中 A,B,CA, B,C 是给定的常数。注意：小猫登上第一班列车前，即从 00 时刻起停留在 11 号站点的那些时刻也算作一次等待。

  • 若小猫最终在时刻 zz 到达 nn 号站点，则烦躁值将再增加 zz。

形式化地说，若小猫共乘坐了 kk 班列车，依次乘坐的列车编号可用序列 s1,s2,⋯ ,sks_1, s_2, \cdots , s_k表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件：

  1. xs1=1x_{s_1} = 1 , ysk=ny_{s_k} = n

  2. 对于所有 j(1≤j<k)j (1 \leq j < k)，满足 ysj=xsj+1y_{s_j} = x_{s_{j+1}} 且 qsj≤psj+1q_{s_j}\leq p_{s_{j+1}}

对于该回家路线，小猫得到的烦躁值将为：

qsk+(A×ps12+B×ps1+C)+∑j=1k−1(A(psj+1−qsj)2+B(psj+1−qsj)+C)q_{s_k}+(A\times p_{s_1}^2+B\times p_{s_1}+C)+\sum_{j=1}^{k-1}(A(p_{s_{j+1}}-q_{s_j})^2+B(p_{s_{j+1}}-q_{s_j})+C)

小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最小的烦躁值。题目保证至少存在一条可行的回家路线。

对于所有测试点：2≤n≤105,1≤m≤2×105,0≤A≤10,0≤B,C≤106,1≤xi,yi≤n,xi≠yi,0≤pi<qi≤1032\le n\le 10^5,1\le m\le 2\times 10^5,0 \le A \le 10 , 0 \le B, C \le 10^6,1 \le x_i, y_i \le n , x_i \neq y_i , 0 \le p_i < q_i \le 10^3。

每个测试点的具体限制见下表：

测试点编号 nn mm A,B,CA,B,C 的特殊限制 其他特殊条件
1∼21\sim 2 ≤100\le 100 =n−1=n-1 无 yi=xi+1y_i=x_i+1
3∼43\sim 4 ^ ≤100\le 100 A=B=C=0A=B=C=0 ^
5∼85\sim 8 ≤2×103\le 2\times 10^3 ≤4×103\le 4\times 10^3 ^ xi<yix_i<y_i
99 ^ ^ A=B=0A=B=0 ^
1010 ^ ^ A=0A=0 ^
11∼1411\sim 14 ^ ^ 无 无
1515 ≤105\le 10^5 ≤2×105\le 2\times 10^5 A=B=0A=B=0 ^
16∼1716\sim 17 ^ ^ A=0A=0 ^
18∼2018\sim 20 ^ ^ 无 ^

太模板了。不过据说考场上一大堆人用 O(mt)O(mt) 或者暴搜 AC 。

代码：

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
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int M=1e6+10,inf=1e18,eps=1e-9;
int st[M],nd[M],p[M],q[M],x[M],y[M],h[M],t[M],dp[M];
vector<int>pos[M],ins[M],Q[M];
void read(int &x){
	int f=1;x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
int pf(int x){return x*x;}
double slope(int i,int j){
	int xx=x[j]-x[i],yy=y[j]-y[i];
	if(!xx){
		if(yy>0)return inf;
		return -inf;
	}
	return yy*1./xx;
}
signed main(){
	int n,m,A,B,C,T=0,ans=inf;
	read(n),read(m),read(A),read(B),read(C);
	for(int i=1;i<=m;i++){
		read(st[i]),read(nd[i]),read(p[i]),read(q[i]);
		T=max(T,q[i]),pos[p[i]].push_back(i);
	}
	for(int i=1;i<=n;i++)h[i]=0,t[i]=-1;
	for(int pi=0;pi<=T;pi++){
		for(int id=0;id<ins[pi].size();id++){
			int i=ins[pi][id],pp=nd[i];
			while(h[pp]<t[pp]&&slope(Q[pp][t[pp]-1],Q[pp][t[pp]])>=slope(Q[pp][t[pp]-1],i))t[pp]--;
			++t[pp];
			if(t[pp]>=Q[pp].size())Q[pp].push_back(i);
			else Q[pp][t[pp]]=i;
		}
		for(int id=0;id<pos[pi].size();id++){
			int i=pos[pi][id],pp=st[i];double k=2.*A*pi;
			while(h[pp]<t[pp]&&slope(Q[pp][h[pp]],Q[pp][h[pp]+1])<k)h[pp]++;
			if(h[pp]>t[pp]&&st[i]!=1)continue;
			int j;
			if(st[i]==1&&h[pp]>t[pp])j=0;
			else j=Q[pp][h[pp]];
			dp[i]=dp[j]+A*pf(p[i]-q[j])+B*(p[i]-q[j])+C;
			x[i]=q[i],y[i]=dp[i]+A*pf(q[i])-B*q[i];
			ins[q[i]].push_back(i);
			if(nd[i]==n)ans=min(ans,dp[i]+q[i]);
		}
	}
	cout<<ans;
	return 0;
}

P5471 [NOI2019] 弹跳

【模板】 K-D Tree 优化建图。

题目链接： [NOI2019] 弹跳 。

题目描述：

跳蚤国有 nn 座城市，分别编号为 1−n1 - n，11 号城市为首都。所有城市分布在一个w×hw \times h 范围的网格上。每座城市都有一个整数坐标 (x,y)(1≤x≤w,1≤y≤h)(x, y) (1 \leq x \leq w, 1 \leq y \leq h)，不同城市的坐标不相同。

在跳蚤国中共有 mm 个弹跳装置，分别编号为 1−m1 - m，其中 ii 号弹跳装置位于 pip_i 号城市，并具有参数 ti,Li,Ri,Di,Uit_i, L_i, R_i, D_i, U_i。利用该弹跳装置，跳蚤可花费 ti(ti>0)t_i (t_i > 0) 个单位时间，从 pip_i 号城市跳至坐标满足 Li≤x≤Ri,Di≤y≤Ui(1≤Li≤Ri≤w,1≤Di≤Ui≤h)L_i \leq x \leq R_i, D_i \leq y \leq U_i (1 \leq L_i \leq R_i \leq w, 1 \leq D_i \leq U_i \leq h) 的任意一座城市。需要注意的是，一座城市中可能存在多个弹跳装置，也可能没有弹跳装置。

由于城市间距离较远，跳蚤们必须依靠弹跳装置出行。具体来说，一次出行将经过
若干座城市，依次经过的城市的编号可用序列 a0,a1,⋯ ,aka_0, a_1, \cdots , a_k 表示；在此次出行中，依次利用的弹跳装置的编号可用序列 b1,b2,⋯ ,bkb_1, b_2, \cdots , b_k 表示。其中每座城市可在序列 {aj}\{a_j\} 中出现任意次，每个弹跳装置也可在序列 {bj}\{b_j\} 中出现任意次，且满足，对于每个 j(1≤j≤k)j (1 \leq j \leq k)，编号为 bjb_j 的弹跳装置位于城市 aj−1a_{j-1}，且跳蚤能通过该弹跳装置跳至城市 aja_j。我们称这是一次从城市 a0a_0 到城市 aka_k 的出行，其进行了 kk 次弹跳，共花费 ∑i=1ktbi\sum^k_{i=1} t_{b_{i}} 个单位时间。

现在跳蚤国王想知道，对于跳蚤国除首都（11 号城市）外的每座城市，从首都出发，到达该城市最少需要花费的单位时间。跳蚤国王保证，对每座城市，均存在从首都到它的出行方案。

测试点编号 1≤n≤1\le n\le 1≤m≤1\le m\le 特殊限制
1∼81\sim8 100100 100100 无
9∼139\sim13 5×1045\times 10^4 10510^5 每个弹跳装置恰好可达一座城市，且 Li=RiL_i=R_i，Di=UiD_i=U_i
14∼1814\sim18 5×1045\times 10^4 10510^5 h=1h=1
19∼2219\sim22 2.5×1042.5\times 10^4 5×1045\times 10^4 无
23∼2523\sim25 7×1047\times 10^4 1.5×1051.5\times 10^5 无

容易写出 5252 分线段树优化建图部分分。

由于这是二维的，所以用 K-D Tree 。

代码：

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
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
const int N = 70000 + 1023 + 114514, M = 150000 + 1023 + 114514;
inline void read(int &x) {x = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ '0');
        c = getchar();
    }
}
struct Node1 {
    int x, y;
} a[N];
struct Node2 {
    int p, t;
    int L, R;
    int D, U;
} b[M];
vector<int> city_b[N];
ll d[N];
bool vis[N];
int lc[N], rc[N];
ll lx[N], rx[N], ly[N], ry[N];
int id[N], tot, val[N];
void maintain(int p) {
    lx[p] = rx[p] = a[p].x;
    ly[p] = ry[p] = a[p].y;
    if (lc[p]) {
        lx[p] = min(lx[p], lx[lc[p]]);
        rx[p] = max(rx[p], rx[lc[p]]);
        ly[p] = min(ly[p], ly[lc[p]]);
        ry[p] = max(ry[p], ry[lc[p]]);
    }
    if (rc[p]) {
        lx[p] = min(lx[p], lx[rc[p]]);
        rx[p] = max(rx[p], rx[rc[p]]);
        ly[p] = min(ly[p], ly[rc[p]]);
        ry[p] = max(ry[p], ry[rc[p]]);
    }
}
inline bool cmpx(const int &x, const int &y) { return a[x].x < a[y].x; }
inline bool cmpy(const int &x, const int &y) { return a[x].y < a[y].y; }
inline void pushup(int p) { val[p] = val[lc[p]] + val[rc[p]] + vis[p]; }
int build(int l, int r, bool idx) {
    if (r < l) return 0;
    int mid = l + r >> 1;
    
    if (idx)
        nth_element(id + l, id + mid, id + r + 1, cmpx);
    else
        nth_element(id + l, id + mid, id + r + 1, cmpy);
    
    int k = id[mid];
    vis[k] = 1;
    lc[k] = build(l, mid - 1, idx ^ 1);
    rc[k] = build(mid + 1, r, idx ^ 1);
    maintain(k);
    pushup(k);
    return k;
}
int query(int p, int l, int r, int d, int u) {
    if (!val[p]) return 0;
    if (r < lx[p] || rx[p] < l || u < ly[p] || ry[p] < d) return 0;
    if (vis[p] && l <= a[p].x && a[p].x <= r && d <= a[p].y && a[p].y <= u) {
        vis[p] = 0;
        pushup(p);
        return p;
    }
    int k = query(lc[p], l, r, d, u);
    if (!k)
        k = query(rc[p], l, r, d, u);
    pushup(p);
    return k;
}
int main() {
    int n, m, w, h;
    read(n), read(m), read(w), read(h);
    for (int i = 1; i <= n; i++) {
        read(a[i].x), read(a[i].y);
        id[i] = i;
        d[i] = inf;
    }
    int t[N], L[N], R[N], D[N], U[N];
    for (int i = 1, p; i <= m; i++) {
        read(p), read(t[i]), read(L[i]), read(R[i]), read(D[i]), read(U[i]);
        city_b[p].push_back(i);
    }
    L[0] = R[0] = a[1].x;
    D[0] = U[0] = a[1].y;
    for (int i = 0; i <= n; i++) {
        lx[i] = ly[i] = 0x3f3f3f3f;
        rx[i] = ry[i] = 0;
    }
    int root = build(1, n, 0);
    #define P pair<ll, int>
    priority_queue<P, vector<P>, greater<P>> q;
    d[1] = 0;
    q.push({0, 0});
    while (!q.empty()) {
        P it1 = q.top();
        q.pop();
        ll dist = it1.first;
        int k = it1.second;
        int u;
        while (u = query(root, L[k], R[k], D[k], U[k])) {
            d[u] = dist;
            for (int v : city_b[u]) {
                q.push({dist + t[v], v});
            }
        }
    }
    for (int i = 2; i <= n; i++)
        printf("%lld\n", d[i]);
    return 0;
}

P8496 [NOI2022] 众数

【模板】线段树合并。

题目链接： [NOI2022] 众数 。

题目描述：

对于一个序列，定义其众数为序列中出现次数严格大于一半的数字。注意该定义与一般的定义有出入，在本题中请以题面中给出的定义为准。

一开始给定 nn 个长度不一的正整数序列，编号为 1∼n1 \sim n，初始序列可以为空。这 nn 个序列被视为存在，其他编号对应的序列视为不存在。

有 qq 次操作，操作有以下类型:

  • 1 x y1 \ x \ y：在 xx 号序列末尾插入数字 yy。保证 xx 号序列存在，且 1≤x,y≤n+q1 \le x, y \le n + q。
  • 2 x2 \ x：删除 xx 号序列末尾的数字，保证 xx 号序列存在、非空，且 1≤x≤n+q1 \le x \le n + q。
  • 3 m x1 x2… xm3 \ m \ x_1 \ x_2 \dots \ x_m：将 x1,x2,…,xmx_1, x_2, \ldots, x_m 号序列顺次拼接，得到一个新序列，并询问其众数。如果不存在满足上述条件的数，则返回 −1-1。数据保证对于任意 1≤i≤m1 \le i \le m，xix_i 是一个仍然存在的序列，1≤xi≤n+q1 \le x_i \le n + q，且拼接得到的序列非空。注意：不保证 x1,…,xm\boldsymbol{x_1, \ldots, x_m} 互不相同，询问中的合并操作不会对后续操作产生影响。
  • 4 x1 x2 x34 \ x_1 \ x_2 \ x_3：新建一个编号为 x3x_3 的序列，其为 x1x_1 号序列后顺次添加 x2x_2 号序列中数字得到的结果，然后删除 x1,x2x_1, x_2 对应的序列。此时序列 x3x_3 视为存在，而序列 x1,x2x_1, x_2 被视为不存在，在后续操作中也不会被再次使用。保证 1≤x1,x2,x3≤n+q1 \le x_1, x_2, x_3 \le n + q、x1≠x2x_1 \ne x_2、序列 x1,x2x_1, x_2 在操作前存在、且在操作前没有序列使用过编号 x3x_3。

对于所有测试数据，保证 1≤n,q,Cm,Cl≤5×1051 \le n, q, C_m, C_l \le 5 \times {10}^5。

n,qn, q Cm,ClC_m, C_l 测试点编号 特殊性质 A 特殊性质 B 特殊性质 C
≤300\le 300 ≤300\le 300 1∼31 \sim 3 否 否 是
≤4000\le 4000 ≤4000\le 4000 4∼74 \sim 7 否 否 是
≤105\le {10}^5 ≤105\le {10}^5 88 是 是 是
≤105\le {10}^5 ≤105\le {10}^5 99 是 否 否
≤105\le {10}^5 ≤105\le {10}^5 1010 否 是 否
≤105\le {10}^5 ≤105\le {10}^5 11∼1211 \sim 12 否 否 是
≤105\le {10}^5 ≤105\le {10}^5 1313 否 否 否
≤5×105\le 5 \times {10}^5 ≤5×105\le 5 \times {10}^5 1414 是 是 是
≤5×105\le 5 \times {10}^5 ≤5×105\le 5 \times {10}^5 1515 是 否 否
≤5×105\le 5 \times {10}^5 ≤5×105\le 5 \times {10}^5 1616 否 是 否
≤5×105\le 5 \times {10}^5 ≤5×105\le 5 \times {10}^5 17∼1817 \sim 18 否 否 是
≤5×105\le 5 \times {10}^5 ≤5×105\le 5 \times {10}^5 19∼2019 \sim 20 否 否 否

特殊性质 A：保证 n=1n = 1 且没有操作 44。
特殊性质 B：保证任意时刻任何序列中只有数字 11 和 22。
特殊性质 C：保证没有操作 22。

题面有点长，不过仍然可以总结为以下操作：

  • 加入/删除一个数。
  • 求众数。
  • 合并序列。

前面两个是权值线段树就能完成的操作，最后一个可以线段树合并。

然后就做完了，据说这是最水 NOI 题目。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=1000010,M=40000010;
#define ll long long
int n,q,L[N],R[N],idx,val[N],ls[M],rs[M],num[M];
int pre[N],b[N],ed[N],id,rt[N],len[N];
void insert(int &p,int l,int r,int x,int y){
	if(!p)p=++idx;
	if(l==r){
		num[p]+=y;
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=x)insert(ls[p],l,mid,x,y);
	else insert(rs[p],mid+1,r,x,y);
	num[p]=num[ls[p]]+num[rs[p]];
}
int merge(int p,int q,int l,int r){
	if(!p||!q)return p+q;
	num[p]+=num[q];
	if(l==r)return p;
	int mid=(l+r)>>1;
	ls[p]=merge(ls[p],ls[q],l,mid);
	rs[p]=merge(rs[p],rs[q],mid+1,r);
	return p;
}
int query(int top,int l,int r,int x){
	if(l==r)return l;
	int mid=(l+r)>>1;
	ll res=0,sum=0;
	for(int i=1;i<=top;i++)sum+=num[b[i]],res+=num[ls[b[i]]];
	if(res>x){
		for(int i=1;i<=top;i++)b[i]=ls[b[i]];
		return query(top,l,mid,x);
	}
	if(sum-res>x){
		for(int i=1;i<=top;i++)b[i]=rs[b[i]];
		return query(top,mid+1,r,x);
	}
	return -1;
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		int l;
		cin>>l;
		len[i]=l;
		for(int j=1;j<=l;j++){
			int x;
			cin>>x;
			val[++id]=x;
			if(!pre[i])pre[i]=ed[i]=id;
			else R[ed[i]]=id,L[id]=ed[i],ed[i]=id;
			insert(rt[i],1,n+q,x,1);
		}
	}
	for(int i=1;i<=q;i++){
		int opt,x,y,z;
		cin>>opt;
		if(opt==1){
			cin>>x>>y;
			val[++id]=y;
			if(!pre[x])pre[x]=ed[x]=id;
			else R[ed[x]]=id,L[id]=ed[x],ed[x]=id;
			len[x]++;
			insert(rt[x],1,n+q,y,1);
		}
		if(opt==2){
			cin>>x;
			insert(rt[x],1,n+q,val[ed[x]],-1);
			ed[x]=L[ed[x]];
			R[ed[x]]=0;
			len[x]--;
			if(!ed[x])pre[x]=ed[x]=0;
		}
		if(opt==3){
			cin>>x;
			ll sum=0;
			for(int j=1;j<=x;j++)cin>>b[j],sum+=len[b[j]],b[j]=rt[b[j]];
			//cout<<sum<<" ";
			cout<<query(x,1,n+q,sum>>1)<<"\n";
		}
		if(opt==4){
			cin>>x>>y>>z;
			rt[z]=merge(rt[x],rt[y],1,n+q);
			len[z]=len[x]+len[y];
			if(!ed[x])pre[z]=pre[y],ed[z]=ed[y];
			else if(!ed[y])pre[z]=pre[x],ed[z]=ed[x];
			else{
				pre[z]=pre[x],ed[z]=ed[y];
				R[ed[x]]=pre[y];
				L[pre[y]]=ed[x];
			}
		}
	}
	return 0;
}

P7735 [NOI2021] 轻重边

不太模板的一个题目，不过也不难，毕竟我也能做出来。

题目链接： [NOI2021] 轻重边 。

题目描述：

小 W 有一棵 nn 个结点的树，树上的每一条边可能是轻边或者重边。接下来你需要对树进行 mm 次操作，在所有操作开始前，树上所有边都是轻边。操作有以下两种：

  1. 给定两个点 aa 和 bb，首先对于 aa 到 bb 路径上的所有点 xx（包含 aa 和 bb），你要将与 xx 相连的所有边变为轻边。然后再将 aa 到 bb 路径上包含的所有边变为重边。
  2. 给定两个点 aa 和 bb，你需要计算当前 aa 到 bb 的路径上一共包含多少条重边。

对于所有测试数据：T≤3T \le 3，1≤n,m≤1051 \le n, m \le {10}^5。

测试点编号 $n, m \le $ 特殊性质
1∼21 \sim 2 1010 无
3∼63 \sim 6 50005000 无
7∼87 \sim 8 105{10}^5 A，B
9∼109 \sim 10 105{10}^5 A
11∼1411 \sim 14 105{10}^5 B
15∼1615 \sim 16 2×1042\times {10}^4 无
17∼2017 \sim 20 105{10}^5 无

特殊性质 A：树的形态是一条链。

特殊性质 B：第 22 类操作给出的 aia_i 和 bib_i 之间有边直接相连。

首先，这个操作很像 LCT ，所以我们可以用 LCT 做。

然后，由于每次要将一段路径上的边变成独一无二的重边。所以我们可以想到给这一段路径上的每个点或边染一个独一无二的颜色。

接着，由于要将这个点的其他边变为轻边，所以这里是对点染色，不是对边染色。

最后，每一段连续的相同颜色段代表着一段重边。每一次颜色切换意味着轻边，所以我们可以求出颜色段数量，最后拿路径总长度减去即可。

还是一个思维流畅的题目。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=400010;
int num[N],lm[N],rm[N],n,m,tag[N],a[N],f[N],sz[N],son[N],dfn[N],fdfn[N],id,top[N],d[N];
vector<int>v[N];
void dfs(int x,int fa){
    f[x]=fa;
    sz[x]=1;
    d[x]=d[fa]+1;
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(u==fa)continue;
        dfs(u,x);
        sz[x]+=sz[u];
        if(sz[u]>sz[son[x]])son[x]=u;
    }
}
void dfs2(int x,int fa){
    dfn[x]=++id;fdfn[id]=x;
    if(son[x])top[son[x]]=top[x],dfs2(son[x],x);
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(u==fa||u==son[x])continue;
        top[u]=u;
        dfs2(u,x);
    }
}
void up(int p){
    num[p]=num[p<<1]+num[p<<1|1]-(rm[p<<1]==lm[p<<1|1]);
    lm[p]=lm[p<<1];rm[p]=rm[p<<1|1];
}
void down(int p){
    if(!tag[p])return ;
    lm[p<<1]=rm[p<<1]=lm[p<<1|1]=rm[p<<1|1]=tag[p<<1]=tag[p<<1|1]=tag[p];
    num[p<<1]=num[p<<1|1]=1;
    tag[p]=0;
}
void change(int p,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){
        num[p]=1;
        tag[p]=x;
        lm[p]=rm[p]=x;
        return ;
    }
    int mid=(l+r)>>1;
    down(p);
    if(mid>=ql)change(p<<1,l,mid,ql,qr,x);
    if(mid<qr)change(p<<1|1,mid+1,r,ql,qr,x);
    up(p);
}
int query(int p,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1;
    down(p);
    if(ql<=mid&&mid<qr){
        return query(p<<1,l,mid,ql,qr)+query(p<<1|1,mid+1,r,ql,qr)-(rm[p<<1]==lm[p<<1|1]);
    }
    else if(ql<=mid)return query(p<<1,l,mid,ql,qr);
    else if(mid<qr)return query(p<<1|1,mid+1,r,ql,qr);
    return 0;
}  
void build(int p,int l,int r){
    if(l==r){
        num[p]=1;lm[p]=rm[p]=a[fdfn[l]];
        return ;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
}
int getl(int p,int l,int r,int x){
    if(l==r){
        return lm[p];
    }
    int mid=(l+r)>>1;
    down(p);
    if(mid>=x)return getl(p<<1,l,mid,x);
    else return getl(p<<1|1,mid+1,r,x);
}
int cnt=0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(cout.tie(0));
    int T;
    cin>>T;
    while(T--){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        f[i]=son[i]=top[i]=sz[i]=d[i]=0;
        v[i].clear();
    }
    for(int i=1;i<=4*n;i++){
        num[i]=lm[i]=rm[i]=tag[i]=0;
    }
        id=0;
    for(int i=1;i<=n;i++)a[i]=i;cnt=n;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);top[1]=1;dfs2(1,0);build(1,1,n);
    while(m--){
        int x,y,z,opt;
        cin>>opt>>x>>y;
        if(opt==1){
            z=++cnt;
            while(top[x]!=top[y]){
                if(d[top[x]]<d[top[y]])swap(x,y);
                change(1,1,n,dfn[top[x]],dfn[x],z);
                x=f[top[x]];
            }
            if(d[x]<d[y])swap(x,y);
            change(1,1,n,dfn[y],dfn[x],z);
        }
        else{
            int ans=0,len=0;
            while(top[x]!=top[y]){
                if(d[top[x]]<d[top[y]])swap(x,y);
                ans+=query(1,1,n,dfn[top[x]],dfn[x]);
                ans-=(getl(1,1,n,dfn[top[x]])==getl(1,1,n,dfn[f[top[x]]]));
                len+=d[x]-d[top[x]]+1;
                x=f[top[x]];
            }
            if(d[x]<d[y])swap(x,y);
            ans+=query(1,1,n,dfn[y],dfn[x]);
            len+=d[x]-d[y]+1;
            cout<<len-ans<<"\n";
        }
    }}
    return 0;
}

P2178 [NOI2015] 品酒大会

【模板】后缀自动机 SAM 。

题目链接： [NOI2015] 品酒大会 。

题目描述：

一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战 两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 nn 杯鸡尾酒。这 nn 杯鸡尾酒排成一行，其中第 ii 杯酒 (1≤i≤n1 \le i \le n) 被贴上了一个标签 sis_i ，每个标签都是 2626 个小写 英文字母之一。设 str(l,r)str(l, r) 表示第 ll 杯酒到第 rr 杯酒的 r−l+1r - l + 1 个标签顺次连接构成的字符串。若 str(p,p0)=str(q,q0)str(p, p_0) = str(q, q_0)，其中 1≤p≤p0≤n1 \le p \le p_0 \le n, 1≤q≤q0≤n1 \le q \le q_0 \le n，p≠qp \ne q，p0−p+1=q0−q+1=rp_0-p+1 = q_0 - q + 1 = r ，则称第 pp 杯酒与第 qq 杯酒是“ rr 相似” 的。当然两杯“rr 相似”（r>1r > 1）的酒同时也是“11 相似”、“22 相似”、……、“(r−1)(r - 1) 相似”的。特别地，对于任意的 1≤p,q≤n,p≠q1 \le p,q \le n,p \ne q，第 pp 杯酒和第 qq 杯酒都 是“00 相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 ii 杯酒 (1≤i≤n1 \le i \le n) 的 美味度为 aia_i 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 pp 杯酒与第 qq 杯酒调兑在一起，将得到一杯美味度为 ap×aqa_p\times a_q 的酒。现在请各位品酒师分别对于 r=0,1,2,…,n−1r = 0,1,2,\dots,n-1，统计出有多少种方法可以 选出 22 杯“rr 相似”的酒，并回答选择 22 杯“rr 相似”的酒调兑可以得到的美味度的最大值。

老套路了。将原串反转后建立后缀自动机，接着线段树处理一下就行。

代码：

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
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=600010;
int n,a[N],len[N],fail[N],son[N][26],sz[N],b[N];
char c[N];
void extend(int c,int C){
    static int rt=1,idx=1;
    int p=rt,cur=++idx;
    len[cur]=len[rt]+1;sz[cur]++;b[cur]=C;
    while(p&&!son[p][c])son[p][c]=cur,p=fail[p];
    if(p){
        int q=son[p][c];
        if(len[p]+1==len[q])fail[cur]=q;
        else{
            int cl=++idx;
            fail[cl]=fail[q];len[cl]=len[p]+1;
            memcpy(son[cl],son[q],sizeof(son[q]));
            while(p&&son[p][c]==q)son[p][c]=cl,p=fail[p];
            fail[cur]=fail[q]=cl;
        }
    }
    else fail[cur]=1;
    rt=cur;
}
vector<int>v[N];
int tag[N<<1],ls[N<<1],rs[N<<1],mx[N<<1],rtA,rtB,idx;
void add(int &p,int l,int r,int ql,int qr,int x){
    if(!p)p=++idx;
    if(ql<=l&&r<=qr){
        tag[p]+=x;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=ql)add(ls[p],l,mid,ql,qr,x);
    if(mid<qr)add(rs[p],mid+1,r,ql,qr,x);
}
void cmax(int &p,int l,int r,int ql,int qr,int x){
    if(!p)p=++idx,mx[p]=-1e18;
    if(ql<=l&&r<=qr){
        mx[p]=max(mx[p],x);
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=ql)cmax(ls[p],l,mid,ql,qr,x);
    if(mid<qr)cmax(rs[p],mid+1,r,ql,qr,x);
}
int query(int p,int l,int r,int x,int ad){
    if(!p)return ad;
    ad+=tag[p];
    if(l==r)return ad;
    int mid=(l+r)>>1;
    if(mid>=x)return query(ls[p],l,mid,x,ad);
    return query(rs[p],mid+1,r,x,ad);
}
int cqmax(int p,int l,int r,int x,int ad){
    if(!p)return ad;
    ad=max(ad,mx[p]);
    if(l==r)return ad;
    int mid=(l+r)>>1;
    if(mid>=x)return cqmax(ls[p],l,mid,x,ad);
    return cqmax(rs[p],mid+1,r,x,ad);
}
int d1[N],d2[N],D1[N],D2[N];
void dfs(int x){
    d1[x]=d2[x]=-1e18;
    D1[x]=D2[x]=1e18;
    if(sz[x]==1){
        d1[x]=D1[x]=b[x];
    }
    for(int u:v[x]){
        dfs(u),sz[x]+=sz[u];
        if(d1[u]>d1[x])d2[x]=d1[x],d1[x]=d1[u];
        else if(d1[u]>d2[x])d2[x]=d1[u];
        if(d2[u]>d2[x])d2[x]=d2[u];
        if(D1[u]<D1[x])D2[x]=D1[x],D1[x]=D1[u];
        else if(D1[u]<D2[x])D2[x]=D1[u];
        if(D2[u]<D2[x])D2[x]=D2[u];
    }
    if(sz[x]>=2){
        add(rtA,0,n,len[fail[x]]+1,len[x],sz[x]*(sz[x]-1)/2);
        cmax(rtB,0,n,len[fail[x]]+1,len[x],max(D1[x]*D2[x],d1[x]*d2[x]));\
    }
}
signed main(){
    cin>>n>>(c+1);
    reverse(c+1,c+1+n);
    for(int i=1;i<=n;i++)cin>>a[n-i+1];
    for(int i=1;i<=n;i++)extend(c[i]-'a',a[i]);
    for(int i=2;fail[i];i++)v[fail[i]].push_back(i);
    len[0]=-1;
    dfs(1);
    for(int i=0;i<n;i++){
        int t=query(rtA,0,n,i,0);int T=(t?cqmax(rtB,0,n,i,-1e18):0);
        cout<<t<<" "<<T<<"\n";
    }
    return 0;
}

P2305 [NOI2014] 购票

【模板】线段树套李超线段树。

题目链接： [NOI2014] 购票 。

题目描述：

今年夏天，NOI 在 SZ 市迎来了她三十周岁的生日。来自全国 nn 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。

全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 nn 个城市用 1∼n1\sim n 的整数编号。其中 SZ 市的编号为 11。对于除 SZ 市之外的任意一个城市 vv，我们给出了它在这棵树上的父亲城市 fvf_v 以及到父亲城市道路的长度 svs_v。

从城市 vv 前往 SZ 市的方法为：选择城市 vv 的一个祖先 aa，支付购票的费用，乘坐交通工具到达 aa。再选择城市 aa 的一个祖先 bb，支付费用并到达 bb。以此类推，直至到达 SZ 市。

对于任意一个城市 vv，我们会给出一个交通工具的距离限制 lvl_v。对于城市 vv 的祖先 A，只有当它们之间所有道路的总长度不超过 lvl_v 时，从城市 vv 才可以通过一次购票到达城市 A，否则不能通过一次购票到达。

对于每个城市 vv，我们还会给出两个非负整数 pv,qvp_v,q_v 作为票价参数。若城市 vv 到城市 A 所有道路的总长度为 dd，那么从城市 vv 到城市 A 购买的票价为 dpv+qvdp_v+q_v。

每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。

对于所有数据，n≤2×105,0≤pv≤106, 0≤qv≤1012, 1≤fv<v, 0<sv≤lv≤2×1011n\leq 2 \times 10^5, 0 \leq p_v \leq 10^6,\ 0 \leq q_v \leq 10^{12},\ 1\leq f_v<v,\ 0<s_v\leq l_v \leq 2 \times 10^{11}，且任意城市到 SZ 市的总路程长度不超过 2×10112 \times 10^{11}。

输入的 tt 表示数据类型，0≤t<40\leq t<4，其中：

  • 当 t=0t=0 或 22 时，对输入的所有城市 vv，都有 fv=v−1f_v=v-1，即所有城市构成一个以 SZ 市为终点的链；
  • 当 t=0t=0 或 11 时，对输入的所有城市 vv，都有 lv=2×1011l_v=2 \times 10^{11}，即没有移动的距离限制，每个城市都能到达它的所有祖先；
  • 当 t=3t=3 时，数据没有特殊性质。

斜率优化板子题，比 NOI2019 的那个还要板。

代码：

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010,M=10000010;
int n,TTT,f[N],ss[N],L[N],P[N],Q[N],d[N],dfn[N],ID,m;
int nxt[N],v[N],w[N],pre[N],id;
int rt[N],s[M],idx,ls[M],rs[M],dp[N],c[N];
void add(int x,int y,int z){
    v[++id]=y;w[id]=z;
    nxt[id]=pre[x],pre[x]=id;
}
void dfs(int x){
    for(int i=pre[x];i;i=nxt[i])dfs(v[i]);
    dfn[x]=++ID;
}
struct dline{
    int k,b;
    dline(){k=b=0;}
    dline(int k,int b):k(k),b(b){}
    int at(int x){return k*x+b;}
}a[N];
void upd(int &p,int l,int r,int x){
    if(!p){p=++idx,s[p]=x;return ;}
    int &y=s[p],mid=(l+r)>>1;
    int t=a[x].at(mid)-a[y].at(mid);
    if(t<0)swap(x,y);
    int tl=a[x].at(l)-a[y].at(l),tr=a[x].at(r)-a[y].at(r);
    if(tl<0)upd(ls[p],l,mid,x);
    if(tr<0)upd(rs[p],mid+1,r,x);
}
int query(int p,int l,int r,int x){
    if(!p)return (int)(1e18);
    if(l==r)return a[s[p]].at(x);
    int mid=(l+r)>>1;
    return min(a[s[p]].at(x),(mid>=x?query(ls[p],l,mid,x):query(rs[p],mid+1,r,x)));
}
void insert(int p,int l,int r,int x,int y){
    upd(rt[p],0,1e6,y);
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(mid>=x)insert(p<<1,l,mid,x,y);
    else insert(p<<1|1,mid+1,r,x,y);
}
int getmin(int p,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr)return query(rt[p],0,1e6,x);
    int mid=(l+r)>>1;
    if(mid>=ql&&mid<qr)return min(getmin(p<<1,l,mid,ql,qr,x),getmin(p<<1|1,mid+1,r,ql,qr,x));
    if(mid>=ql)return getmin(p<<1,l,mid,ql,qr,x);
    return getmin(p<<1|1,mid+1,r,ql,qr,x);
}
void dfs2(int x){
    a[dfn[x]]=dline(-d[m],dp[x]);
    insert(1,1,n,dfn[x],dfn[x]);
    c[m]=x;
    for(int i=pre[x];i;i=nxt[i]){
        m++;d[m]=d[m-1]+ss[v[i]];        
        dp[v[i]]=getmin(1,1,n,dfn[v[i]],dfn[c[lower_bound(d,d+m,d[m]-L[v[i]])-d]],P[v[i]]);
        dp[v[i]]+=Q[v[i]]+d[m]*P[v[i]];
        dfs2(v[i]);m--;
    }
}
signed main(){
    cin>>n>>TTT;
    for(int i=2;i<=n;i++){
        cin>>f[i]>>ss[i]>>P[i]>>Q[i]>>L[i];
        add(f[i],i,ss[i]);
    }
    dfs(1);dfs2(1);
    for(int i=2;i<=n;i++)cout<<dp[i]<<"\n";
    return 0;
}

P2387 [NOI2014] 魔法森林

【模板】动态最小生成树。

题目链接： [NOI2014] 魔法森林 。

题目描述：

为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含 nn 个节点 mm 条边的无向图，节点标号为 1,2,3,…,n1,2,3,…,n，边标号为 1,2,3,…,m1,2,3,…,m。初始时小 E 同学在 11 号节点，隐士则住在 nn 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。

魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 11 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。

只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 eie_i 包含两个权值 aia_i 与 bib_i。若身上携带的 A 型守护精灵个数不少于 aia_i，且 B 型守护精灵个数不少于 bib_i，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小 E 发起攻击，他才能成功找到隐士。

由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。

有 Kruskal 可以证明，答案是对 aa 排序后，逐步加边维护 bb 的最小生成树。

显然可以 LCT 维护。

代码：

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 N=300010,M=400010;
int num[N],val[N],f[N],n,m,id[N],son[N][2],tag[N],s[N],top,Son[N][2],Val[N],Num[N];
void up(int p){
    num[p]=val[p],id[p]=p;
    if(num[son[p][0]]>num[p])num[p]=num[son[p][0]],id[p]=id[son[p][0]];
    if(num[son[p][1]]>num[p])num[p]=num[son[p][1]],id[p]=id[son[p][1]];
    Num[p]=max(max(Num[son[p][0]],Num[son[p][1]]),Val[p]);
}
int dir(int p){return p==son[f[p]][1];}
int isr(int p){return p!=son[f[p]][1]&&p!=son[f[p]][0];}
void rotate(int x){
    int y=f[x],z=f[f[x]],s=dir(x);
    if(!isr(y))son[z][dir(y)]=x;
    son[y][s]=son[x][s^1];
    if(son[x][s^1])f[son[x][s^1]]=y;
    son[x][s^1]=y;
    f[y]=x;f[x]=z;
    up(y);up(x);
}
void down(int p){
    if(!tag[p])return ;
    if(son[p][0])tag[son[p][0]]^=1;
    if(son[p][1])tag[son[p][1]]^=1;
    swap(son[p][0],son[p][1]);
    tag[p]=0;
}
void splay(int x){
    s[top=1]=x;
    for(int y=x;!isr(y);y=f[y])s[++top]=f[y];
    while(top)down(s[top--]);
    while(!isr(x)){
        int y=f[x];
        if(!isr(y))rotate(dir(y)==dir(x)?y:x);
        rotate(x);
    }
}
void access(int x){
    for(int y=0;x;x=f[y=x]){
        splay(x);son[x][1]=y;up(x);
    }
}
void make(int x){
    access(x);splay(x);tag[x]^=1;
}
void split(int x,int y){
    make(x);access(y);splay(y);
}
void link(int x,int y){
    make(x);f[x]=y;
}
void cut(int x,int y){
    split(x,y);
    f[x]=0;son[y][0]=0;
    up(y);
}
int get(int x){
    access(x);splay(x);
    while(son[x][0])x=son[x][0];
    return x;
}
struct node{
    int u,v,a,b;
}q[M];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>q[i].u>>q[i].v>>q[i].a>>q[i].b;
    }
    sort(q+1,q+1+m,[](node x,node y){
        return x.a==y.a?x.b<y.b:x.a<y.a;
    });
    int cnt=n,ans=1e9;
    for(int i=1;i<=m;i++){
        int x=q[i].u,y=q[i].v;
        if(get(x)!=get(y)){
            cnt++;
            num[cnt]=q[i].b,val[cnt]=q[i].b;id[cnt]=cnt;
            Val[cnt]=Num[cnt]=q[i].a,id[cnt]=cnt;
            Son[cnt][0]=x,Son[cnt][1]=y;
            link(cnt,x);
            link(cnt,y);
            if(get(1)==get(n)){
                split(1,n);
                ans=min(ans,Num[n]+num[n]);
            }
        }
        else{
            split(x,y);
            int tnum=num[y],tid=id[y];
            if(tnum>q[i].b){
                cut(tid,Son[tid][0]);
                cut(tid,Son[tid][1]);
                cnt++;
                num[cnt]=q[i].b,val[cnt]=q[i].b;id[cnt]=cnt;
                Val[cnt]=Num[cnt]=q[i].a,id[cnt]=cnt;
                Son[cnt][0]=x,Son[cnt][1]=y;
                link(cnt,x);
                link(cnt,y);
                if(get(1)==get(n)){
                    split(1,n);
                    ans=min(ans,Num[n]+num[n]);
                }
            }
        }
    }
    if(get(1)!=get(n))cout<<"-1\n";
    else{
        cout<<ans<<"\n";
    }
    return 0;
}

P2375 [NOI2014] 动物园

【模板】 KMP 。

题目链接： [NOI2014] 动物园 。

题目描述：

对于一个字符串 SS 的每一个前缀，求出他的最长公共不重叠前后缀长度。答案通过特殊方式处理。

如果对 KMP 自动机有所了解的话就可以随便 AC 了。

代码：

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005,P=1000000007;
int T,nxt[N],num[N],sum[N];
char c[N];
signed main(){
    cin>>T;
    while(T--){
        memset(sum,0,sizeof(sum));
        memset(nxt,0,sizeof(nxt));
        cin>>c;
        int len=strlen(c);
        sum[1]=1;
        for(int i=1,j=0;i<len;i++){
            while(j&&c[i]!=c[j])j=nxt[j];
            if(c[i]==c[j])j++;
            nxt[i+1]=j;
            sum[i+1]=sum[j]+1;
        }
        for(int i=1,j=0;i<len;i++){
            while(j&&c[i]!=c[j])j=nxt[j];
            if(c[i]==c[j])j++;
            while((j*2)>(i+1))j=nxt[j];
            num[i+1]=sum[j];
        }
        int ans=1;
        for(int i=1;i<=len;i++)ans=(ans*(num[i]+1))%P;
        cout<<ans<<'\n';
        //for(int i=1;i<=len;i++)cout<<num[i]<<" ";cout<<"\n";
    }
    return 0;
}

P2704 [NOI2001] 炮兵阵地

【模板】状压 DP 。

题目链接： [NOI2001] 炮兵阵地 。

题目描述：

司令部的将军们打算在 N×MN\times M 的网格地图上部署他们的炮兵部队。

一个 N×MN\times M 的地图由 NN 行 MM 列组成，地图的每一格可能是山地（用 H\texttt{H} 表示），也可能是平原（用 P\texttt{P} 表示），如下图。

在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。

图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。

现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

对于 100%100\% 的数据，1≤N≤1001 \leq N\le 100，1≤M≤101 \leq M\le 10，保证字符仅包含 P 与 H。

简单题。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=101,M=11,inf=0x3f3f3f3f;
int n,m;
int a[N],s[N],cnt[N],id;
int f[N][1<<6][1<<6];
char c;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c;
			if(c=='H')a[i]+=(1<<j-1);
		} 
	}
	for(int i=0;i<(1<<m);i++){
		if((i&(i<<1))==0&&(i&(i<<2))==0&&(i&(i>>1))==0&&(i&(i>>2))==0 ){
			s[++id]=i;
			int t=i;
			while(t){
				t&=(t-1);
				cnt[id]++;
			}
			if((a[1]&i)==0){
				f[1][0][id]=cnt[id];
			}
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=id;i++){
			if((a[k]&s[i])!=0)continue;
			for(int j=1;j<=id;j++){
				if((s[i]&s[j])!=0)continue;
				for(int r=1;r<=id;r++){
					if((s[i]&s[r])!=0)continue;
					if((s[j]&s[r])!=0)continue;
					f[k][j][i]=max(f[k][j][i],f[k-1][r][j]+cnt[i]);
				}
			}
		}		
	}
	int ans=0;
	for(int i=1;i<=id;i++){
		for(int j=1;j<=id;j++){
			ans=max(ans,f[n][i][j]);
		}
	}
	cout<<ans;
	return 0;
}

P3825 [NOI2017] 游戏

【模板】 2-SAT 。

题目链接： [NOI2017] 游戏 。

题目描述：

小 L 计划进行 nn 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 AA、BB、CC 表示。地图一共有四种，分别用小写字母 xx、aa、bb、cc 表示。

其中，赛车 AA 不适合在地图 aa 上使用，赛车 BB 不适合在地图 bb 上使用，赛车 CC 不适合在地图 cc 上使用，而地图 xx 则适合所有赛车参加。

适合所有赛车参加的地图并不多见，最多只会有 dd 张。

nn 场游戏的地图可以用一个小写字母组成的字符串描述。例如：S=xaabxcbcS=\texttt{xaabxcbc} 表示小 L 计划进行 88 场游戏，其中第 11 场和第 55 场的地图类型是 xx，适合所有赛车，第 22 场和第 33 场的地图是 aa，不适合赛车 AA，第 44 场和第 77 场的地图是 bb，不适合赛车 BB，第 66 场和第 88 场的地图是 cc，不适合赛车 CC。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $ (i, h_i, j, h_j) $ 来描述，表示若在第 ii 场使用型号为 hih_i 的车子，则第 jj 场游戏要使用型号为 hjh_j 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。

如果无解，输出 -1。

测试点编号 nn dd mm 其他性质
11 ≤2\le 2 00 ≤4\le 4 无
22 ≤2\le 2 ≤n\le n ≤4\le 4 无
33 ≤5\le 5 00 ≤10\le 10 无
44 ≤5\le 5 ≤n\le n ≤10\le 10 无
55 ≤10\le 10 00 ≤20\le 20 无
66 ≤10\le 10 ≤8\le 8 ≤20\le 20 无
77 ≤20\le 20 00 ≤40\le 40 SS 中只包含 cc
88 ≤20\le 20 00 ≤40\le 40 无
99 ≤20\le 20 ≤8\le 8 ≤40\le 40 SS 中只包含 xx 或 cc
1010 ≤20\le 20 ≤8\le 8 ≤40\le 40 无
1111 ≤100\le 100 00 ≤200\le 200 SS 中只包含 cc
1212 ≤100\le 100 00 ≤200\le 200 无
1313 ≤100\le 100 ≤8\le 8 ≤200\le 200 SS 中只包含 xx 或 cc
1414 ≤100\le 100 ≤8\le 8 ≤200\le 200 无
1515 ≤5×103\le 5\times 10^3 00 ≤104\le 10^4 无
1616 ≤5×103\le 5\times 10^3 ≤8\le 8 ≤104\le 10^4 SS 中只包含 xx 或 cc
1717 ≤5×103\le 5\times 10^3 ≤8\le 8 ≤104\le 10^4 无
1818 ≤5×104\le 5\times 10^4 00 ≤105\le 10^5 无
1919 ≤5×104\le 5\times 10^4 ≤8\le 8 ≤105\le 10^5 SS 中只包含 xx 或 cc
2020 ≤5×104\le 5\times 10^4 ≤8\le 8 ≤105\le 10^5 无

也没啥好说的，唯一要注意的点是要对于 x 枚举 a,b,c 。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,low[N],num[N],idx,cnt,top,s[N],scc[N],in[N];
int a[N],ii[N],hi[N],hj[N],jj[N],flag;
bool book[3][3]={
0,0,1,
0,0,1,
0,1,0
};
char fb[3][2]={
'B','C',
'A','C',
'A','B'
},res[N];
vector<int>v[N];
void dfs(int x,int fa){
    num[x]=low[x]=++idx;
    s[++top]=x;
    in[x]=1;
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i];
        if(!num[u]){
            dfs(u,x);
            low[x]=min(low[x],low[u]);
        }
        else if(in[u]){
            low[x]=min(low[x],num[u]);
        }
    }
    if(low[x]==num[x]){
        int t;
        cnt++;
        do{
            t=s[top--];
            scc[t]=cnt;
            in[t]=0;
        }while(x!=t);
    }
}
void dfs1(int x){
    if(flag)return ;
    if(x==n+1){
idx=0;top=0;cnt=0;
for(int i=0;i<2*n;i++){
    v[i].clear();in[i]=0;
    low[i]=num[i]=0;
    scc[i]=0;
}
for(int i=1;i<=m;i++){
    int X=ii[i],Y=jj[i];
    if(a[X]==hi[i])continue;
    if(a[Y]==hj[i]){
        int t=book[a[X]-1][hi[i]-1];
        v[(X-1)<<1|(t)].push_back((X-1)<<1|(!t));
        continue;
    }
    int t1=book[a[X]-1][hi[i]-1],t2=book[a[Y]-1][hj[i]-1];
    v[(X-1)<<1|(t1)].push_back((Y-1)<<1|(t2));
    v[(Y-1)<<1|(!t2)].push_back((X-1)<<1|(!t1));
}
for(int i=0;i<2*n;i++){
    if(!num[i])dfs(i,0);
}
for(int i=1;i<=n;i++){
    if(scc[(i-1)<<1]==scc[(i-1)<<1|1]){
        return ;
    }
}
flag=1;
for(int i=1;i<=n;i++)res[i]=fb[a[i]-1][(scc[(i-1)<<1|1]<scc[(i-1)<<1])];
        return ;
    }
    if(a[x])dfs1(x+1);
    else{
    a[x]=1;
    dfs1(x+1);
    a[x]=2;
    dfs1(x+1);
    a[x]=0;
    }
}
int main(){
    ios::sync_with_stdio(false);
    int mm;
    cin>>n>>mm;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=(c=='x'?0:(c-'a'+1));
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        char a,b;
        cin>>ii[i]>>a>>jj[i]>>b;
        hi[i]=a-'A'+1;hj[i]=b-'A'+1;
    }
    dfs1(1);
    if(flag){
        for(int i=1;i<=n;i++)cout<<res[i];
    }else cout<<"-1";
    return 0;
}

P4008 [NOI2003] 文本编辑器

【模板】平衡树。

题目链接： [NOI2003] 文本编辑器 。

题目描述：

很久很久以前，DOS 3.x 的程序员们开始对 EDLIN 感到厌倦。于是，人们开始纷纷改用自己写的文本编辑器⋯⋯

多年之后，出于偶然的机会，小明找到了当时的一个编辑软件。进行了一些简单的测试后，小明惊奇地发现：那个软件每秒能够进行上万次编辑操作（当然，你不能手工进行这样的测试）！于是，小明废寝忘食地想做一个同样的东西出来。你能帮助他吗？

为了明确目标，小明对“文本编辑器”做了一个抽象的定义：

文本：由 00 个或多个 ASCII 码在闭区间 [32,126]\left[32,126\right] 内的字符构成的序列。

光标：在一段文本中用于指示位置的标记，可以位于文本首部，文本尾部或文本的某两个字符之间。

文本编辑器：由一段文本和该文本中的一个光标组成的，支持如下操作的数据结构。如果这段文本为空，我们就说这个文本编辑器是空的。

操作名称 输入文件中的格式 功能
Move(k)\text{Move}(k) Move k 将光标移动到第 kk 个字符之后，如果 k=0k=0，将光标移到文本开头。
Insert(n,s)\text{Insert}(n,s) Insert n s 在光标处插入长度为 nn 的字符串 ss，光标位置不变 保证 n≥1n\geq1。
Delete(n)\text{Delete}(n) Delete n 删除光标后的 nn 个字符，光标位置不变，保证 n≥1n \geq 1。
Get(n)\text{Get}(n) Get n 输出光标后的 nn 个字符，光标位置不变，保证 n≥1n \geq 1。
Prev()\text{Prev}() Prev 光标前移一个字符。
Next()\text{Next}() Next 光标后移一个字符。

你的任务是：

  • 建立一个空的文本编辑器。

  • 从输入文件中读入一些操作并执行。

  • 对所有执行过的 GET 操作，将指定的内容写入输出文件。

全都是平衡树操作。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=3000010;
int dat[N],val[N],son[N][2],sz[N],rt,n,pos,idx;
void up(int p){
    sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
void split(int p,int x,int &l,int &r){
    if(!p){
        l=r=0;
        return ;
    }
    if(sz[son[p][0]]<x){
        l=p;
        split(son[p][1],x-1-sz[son[p][0]],son[p][1],r);
    }
    else{
        r=p;
        split(son[p][0],x,l,son[p][0]);
    }
    up(p);
}
int merge(int l,int r){
    if(!l||!r)return l+r;
    if(dat[l]>dat[r]){
        son[l][1]=merge(son[l][1],r);
        up(l);
        return l;
    }
    else{
        son[r][0]=merge(l,son[r][0]);
        up(r);
        return r;
    }
}
void inorder(int p){
    if(!p)return ;
    inorder(son[p][0]);
    cout<<(char)val[p];
    inorder(son[p][1]);
}
int main(){
    srand(time(NULL));
    cin>>n;
    while(n--){
        string c;
        int x;
        cin>>c;
        if(c=="Move"){
            cin>>x;
            pos=x;
        }
        if(c=="Prev"){
            pos--;
        }
        if(c=="Next"){
            pos++;
        }
        if(c=="Insert"){
            int l,r;
            cin>>x;
            split(rt,pos,l,r);
            for(int i=1;i<=x;i++){
                char ch=getchar();
                while(ch<32||ch>126)ch=getchar();
                val[++idx]=ch;
                sz[idx]=1;
                dat[idx]=rand();
                l=merge(l,idx);
            }
            rt=merge(l,r);
        }
        if(c=="Delete"){
            cin>>x;
            int l,p,r;
            split(rt,pos+x,l,r);
            split(l,pos,l,p);
            rt=merge(l,r);
        }
        if(c=="Get"){
            cin>>x;
            int l,p,r;
            split(rt,pos+x,l,r);
            split(l,pos,l,p);
            inorder(p);
            cout<<"\n";
            rt=merge(merge(l,p),r);
        }
    }
    return 0;
}

P4027 [NOI2007] 货币兑换

不想评价了，又是【模板】斜率优化。

题目链接： [NOI2007] 货币兑换 。

题目描述：

小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：A 纪念券（以下简称 A 券）和 B 纪念券（以下简称 B 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 KK 天中 A 券和 B 券的价值分别为 AKA_K 和 BKB_K（元/单位金券）。

为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。

比例交易法分为两个方面：

a) 卖出金券：顾客提供一个 [0,100][0, 100] 内的实数 OPOP 作为卖出比例，其意义为：将 OP%OP\% 的 A 券和 OP%OP\% 的 B 券以当时的价值兑换为人民币；

b) 买入金券：顾客支付 IPIP 元人民币，交易所将会兑换给用户总价值为 IPIP 的金券，并且，满足提供给顾客的 A 券和 B 券的比例在第 KK 天恰好为 RateK\mathrm{Rate}_ K；

例如，假定接下来 33 天内的 AK,BK,RateKA_K,B_K,\mathrm{Rate}_ K 的变化分别为：

时间 AKA_K BKB_K RateK\mathrm{Rate}_ K
第一天 11 11 11
第二天 11 22 22
第三天 22 22 33

假定在第一天时，用户手中有 100100 元人民币但是没有任何金券。

用户可以执行以下的操作：

时间 用户操作 人民币(元) A 券的数量 B 券的数量
开户 无 100100 00 00
第一天 买入 100100 元 00 5050 5050
第二天 卖出 50%50\% 7575 2525 2525
第二天 买入 6060 元 1515 5555 4040
第三天 卖出 100%100\% 205205 00 00

注意到，同一天内可以进行多次操作。

小 Y 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 NN 天内的 A 券和 B 券的价值以及 Rate\mathrm{Rate}。他还希望能够计算出来，如果开始时拥有 SS 元钱，那么 NN 天后最多能够获得多少元钱。

测试数据设计使得精度误差不会超过 10−710^{-7} 。

对于 40%40\% 的测试数据，满足 N≤10N \le 10。

对于 60%60\% 的测试数据，满足 N≤1000N \le 1 000。

对于 100%100\% 的测试数据，满足 N≤105N \le 10^5。

对于 100%100\% 的测试数据，满足：

0<AK≤100 < A_K \leq 10，0<BK≤100 < B_K\le 10，0<RateK≤1000 < \mathrm{Rate}_K \le 100，MaxProfit≤109\mathrm{MaxProfit} \leq 10^9。

输入文件可能很大，请采用快速的读入方式。

必然存在一种最优的买卖方案满足：

每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。

……

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=400010;
const double eps=1e-9;
int n,S,s[N],ss;
double a[N],b[N],Rak[N],f[N],am[N];
struct dline{
    double k,b;
    dline(){k=b=0;}
    dline(double k,double b):k(k),b(b){}
    double at(double x){return k*x+b;}
}c[N];
int get(double x){return lower_bound(am+1,am+1+ss,x)-am;}
int sign(double x){
    if(fabs(x)<eps)return 0;
    return x>0?1:-1;
}
void upd(int p,int l,int r,int x){
    int &y=s[p],mid=(l+r)>>1;
    int t=sign(c[x].at(am[mid])-c[y].at(am[mid]));
    if(t==1)swap(x,y);
    int tl=sign(c[x].at(am[l])-c[y].at(am[l])),tr=sign(c[x].at(am[r])-c[y].at(am[r]));
    if(tl==1)upd(p<<1,l,mid,x);
    if(tr==1)upd(p<<1|1,mid+1,r,x);
}
#define PDI pair<double,int>
PDI Max(PDI x,PDI y){
    return sign(x.first-y.first)>0?x:y;
}
PDI query(int p,int l,int r,int x){
    if(l==r)return {c[s[p]].at(am[x]),s[p]};
    int mid=(l+r)>>1;
    return Max({c[s[p]].at(am[x]),s[p]},(mid>=x?query(p<<1,l,mid,x):query(p<<1|1,mid+1,r,x)));
}
int main(){
    cin>>n>>S;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>Rak[i];
    for(int i=1;i<=n;i++){
        am[++ss]=-a[i]/b[i];
    }
    sort(am+1,am+1+ss);
    f[1]=S;
    c[1]=dline(-f[1]*Rak[1]/(a[1]*Rak[1]+b[1]),f[1]/(a[1]*Rak[1]+b[1]));
    c[0]=dline(0,-1e18);
    upd(1,1,ss,1);
    for(int i=2;i<=n;i++){
        int j=query(1,1,ss,get(-a[i]/b[i])).second;
        f[i]=max(f[i-1],f[j]*(a[i]*Rak[j]+b[i])/(a[j]*Rak[j]+b[j]));
        c[i]=dline(-f[i]*Rak[i]/(a[i]*Rak[i]+b[i]),f[i]/(a[i]*Rak[i]+b[i]));
        upd(1,1,ss,i);
    }
    printf("%.4lf",f[n]);
    return 0;
}

P4774 [NOI2018] 屠龙勇士

【模板】扩展中国剩余定理 exCRT 。

题目描述： [NOI2018] 屠龙勇士 。

题目描述：

小 D 最近在网上发现了一款小游戏。游戏的规则如下：

  • 游戏的目标是按照编号 1→n1 \rightarrow n 顺序杀掉 nn 条巨龙，每条巨龙拥有一个初始的生命值 aia_i 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 pip_i ，直至生命值非负。只有在攻击结束后且当生命值 恰好 为 00 时它才会死去。
  • 游戏开始时玩家拥有 mm 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

  • 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 攻击力最低 的一把剑作为武器。
  • 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 xx 次，使巨龙的生命值减少 x×ATKx \times ATK 。
  • 之后，巨龙会不断使用恢复能力，每次恢复 pip_i 生命值。若在使用恢复能力前或某一次恢复后其生命值为 00 ，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 xx 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 −1-1 即可。

测试点编号 nn mm pip_i aia_i 攻击力 其他限制
1 ≤105\le 10^5 =1=1 =1=1 ≤105\le 10^5 =1=1 无
2 ^ ^ ^ ^ ^ ^
3 ^ ^ ^ ^ ≤105\le 10^5 ^
4 ^ ^ ^ ^ ^ ^
5 ≤103\le 10^3 ≤103\le 10^3 ≤105\le 10^5 ^ ^ 特性 1、特性 2
6 ^ ^ ^ ^ ^ ^
7 ^ ^ ^ ^ ^ ^
8 =1=1 =1=1 ≤108\le 10^8 ≤108\le 10^8 ≤106\le 10^6 特性 1
9 ^ ^ ^ ^ ^ ^
10 ^ ^ ^ ^ ^ ^
11 ^ ^ ^ ^ ^ ^
12 ^ ^ ^ ^ ^ ^
13 ^ ^ ^ ^ ^ ^
14 =105=10^5 =105=10^5 =1=1 ^ ^ 无特殊限制
15 ^ ^ ^ ^ ^ ^
16 ≤105\le 10^5 ^ 所有 pip_i 是质数 ≤1012\le 10^{12} ^ 特性 1
17 ^ ^ ^ ^ ^ ^
18 ^ ^ 无特殊限制 ^ ^ ^
19 ^ ^ ^ ^ ^ ^
20 ^ ^ ^ ^ ^ ^

特性 1 是指：对于任意的 ii，ai≤pia_i \le p_i。

特性 2 是指：lcm⁡(pi)≤106\operatorname{lcm}(p_i) \le 10^6，即所有 pip_i 的 最小公倍数 不大于 10610^6。

对于所有的测试点，T≤5T \le 5，所有武器的攻击力 ≤106\le 10^6，所有 pip_i 的最小公倍数 ≤1012\le 10^{12}。

保证 $ T, n, m $ 均为正整数。

说白了，就是在原本的 exCRT 基础上加了个系数，随便改一下就行。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
#define ll long long
#define int __int128
ll T,n,m,a[N],p[N],b[N],c[N];
void exgcd(int a,int b,int &x,int &y){
    if(b==0)return (void)(x=1,y=0);
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
multiset<int>s;
ll exCRT(){
    int ans=0,M=1,mx=0;
    for(int i=1;i<=m;i++)s.insert(c[i]);
    for(int i=1;i<=n;i++){
        set<int>::iterator it=s.upper_bound(a[i]);
        int t;
        if(it==s.begin())t=*s.begin(),s.erase(*s.begin());
        else --it,t=*it,s.erase(it);
        mx=max(mx,(a[i]+t-1)/t);
        int ansA=0,ansB=0,tt=gcd(t*M,p[i]),MM=lcm(M,p[i]/gcd(p[i],t));
        int x=a[i]-t*ans;
        if(x/tt*tt!=x)return -1;
        exgcd(t*M,p[i],ansA,ansB);
        ansA=(ansA%MM+MM)%MM;
        ans=((x/tt*ansA%MM*M%MM+MM)%MM+ans)%MM;
        M=MM;
        s.insert(b[i]);
    }
    if(ans<mx)ans+=((mx-ans-1)/M+1)*M;
    return ans;
}
signed main(){
    cin>>T;
    while(T--){
        s.clear();
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>p[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        for(int i=1;i<=m;i++)cin>>c[i];
        cout<<exCRT()<<"\n";
    }
    return 0;
}

P4768 [NOI2018] 归程

【模板】可持久化并查集。

题目链接： [NOI2018] 归程 。

题目描述：

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 nn 个节点、mm 条边的无向连通图（节点的编号从 11 至 nn）。我们依次用 l,al,a 描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在魔力之都的 11 号节点。对于接下来 QQ 天，每一天 Yazid 都会告诉你他的出发点 vv，以及当天的水位线 pp。

每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是，第二天车会被重置，这意味着：

  • 车会在新的出发点被准备好。
  • Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

所有测试点均保证 T≤3T\leq 3，所有测试点中的所有数据均满足如下限制：

  • n≤2×105n\leq 2\times 10^5，m≤4×105m\leq 4\times 10^5，Q≤4×105Q\leq 4\times 10^5，K∈{0,1}K\in\left\{0,1\right\}，1≤S≤1091\leq S\leq 10^9。
  • 对于所有边：l≤104l\leq 10^4，a≤109a\leq 10^9。
  • 任意两点之间都直接或间接通过边相连。

为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：

  • 图形态：对于表格中该项为“一棵树”或“一条链”的测试点，保证 m=n−1m = n-1。除此之外，这两类测试点分别满足如下限制：
    • 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
    • 一条链：保证所有边满足 u+1=vu + 1 = v。
  • 海拔：对于表格中该项为“一种”的测试点，保证对于所有边有 a=1a = 1。
  • 强制在线：对于表格中该项为“是”的测试点，保证 K=1K = 1；如果该项为“否”，则有 K=0K = 0。
  • 对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。
nn mm QQ 测试点 形态 海拔 强制在线
≤1\leq 1 ≤0\leq 0 00 1 不保证 一种 否
≤6\leq 6 ≤10\leq 10 1010 2 ^ ^ ^
≤50\leq 50 ≤150\leq 150 100100 3 ^ ^ ^
≤100\leq 100 ≤300\leq 300 200200 4 ^ ^ ^
≤1500\leq 1500 ≤4000\leq 4000 20002000 5 ^ ^ ^
≤200000\leq 200000 ≤400000\leq 400000 100000100000 6 ^ ^ ^
≤1500\leq 1500 =n−1=n-1 20002000 7 一条链 不保证 ^
^ ^ ^ 8 ^ ^ ^
^ ^ ^ 9 ^ ^ ^
≤200000\leq 200000 ^ 100000100000 10 一棵树 ^ ^
^ ^ ^ 11 ^ ^ 是
^ ≤400000\leq 400000 ^ 12 不保证 ^ 否
^ ^ ^ 13 ^ ^ ^
^ ^ ^ 14 ^ ^ ^
≤1500\leq 1500 ≤4000\leq 4000 20002000 15 ^ ^ 是
^ ^ ^ 16 ^ ^ ^
≤200000\leq 200000 ≤400000\leq 400000 100000100000 17 ^ ^ ^
^ ^ ^ 18 ^ ^ ^
^ ^ 400000400000 19 ^ ^ ^
^ ^ ^ 20 ^ ^ ^

可以发现，如果可以离线的话，按海拔高度离线加入并查集维护联通性和整个联通块中里目标最近的顶点就行，具体可以使用 Dijkstra 求最短路后对每个顶点维护，合并时取 min 即可。

然后在线的话就是可持久化并查集了。

代码：

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
#include <bits/stdc++.h>
using namespace std;
const int N=20000010,M=1000010,K=400010;
int n,f[M],d[M],val[N],ls[N],rs[N],m,idx,T,dis[K],rt[M],book[K],am[N],Q,k,s;
vector<int>v[K];
struct node{
    int u,v,l,a;
}q[K];
bool operator<(node x,node y){
    return x.a<y.a;
}
void copy(int x,int y){ls[x]=ls[y];rs[x]=rs[y];val[x]=val[y];}
int insert(int p,int l,int r,int x,int y){
    idx++;copy(idx,p);p=idx;
    if(l==r){
        val[p]=y;
        return p;
    }
    int mid=(l+r)>>1;
    if(mid>=x)ls[p]=insert(ls[p],l,mid,x,y);
    else rs[p]=insert(rs[p],mid+1,r,x,y);
    return p;
}
int query(int p,int l,int r,int x){
    if(l==r)return val[p];
    int mid=(l+r)>>1;
    if(mid>=x)return query(ls[p],l,mid,x);
    return query(rs[p],mid+1,r,x);
}
int build(int p,int l,int r,int t){
    p=++idx;
    if(l==r){
        val[p]=(t==0?l:(t==1?0:dis[l]));
        return p;
    }
    int mid=(l+r)>>1;
    ls[p]=build(p,l,mid,t);
    rs[p]=build(p,mid+1,r,t);
    return p;
}
int getf(int v,int x){
    int t=query(f[v],1,n,x);
    return t==x?x:getf(v,t);
}
void add(int x,int y,int v){
    int fx=getf(v,x),fy=getf(v,y);
    if(fx!=fy){
        int dx=query(d[v],1,n,fx),dy=query(d[v],1,n,fy);
        int disx=query(rt[v],1,n,fx),disy=query(rt[v],1,n,fy);
        if(dx<dy)swap(fx,fy),swap(dx,dy),swap(disx,disy);
        f[v-1]=insert(f[v],1,n,fy,fx);
        if(disx>disy)rt[v-1]=insert(rt[v],1,n,fx,disy);
        else rt[v-1]=rt[v];
        if(dx==dy)d[v-1]=insert(d[v],1,n,fx,dx+1);
        else d[v-1]=d[v];
    }
    else f[v-1]=f[v],d[v-1]=d[v],rt[v-1]=rt[v];
}
void dijkstra(){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    for(int i=1;i<=n;i++)dis[i]=(2e9+1000),book[i]=0;
    dis[1]=0;
    q.push({0,1});
    while(!q.empty()){
        int x=q.top().second;
        q.pop();
        if(book[x])continue;
        book[x]=1;
        for(int i=0;i<v[x].size();i+=2){
            int u=v[x][i],w=v[x][i+1];
            if(book[u])continue;
            if(dis[u]>dis[x]+w){
                dis[u]=dis[x]+w;
                q.push({dis[u],u});
            }
        }
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<=idx;i++)ls[i]=rs[i]=val[i]=0;
        idx=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=m+2;i++){
            f[i]=d[i]=rt[i]=0;
        }
        for(int i=1;i<=n;i++){
            v[i].clear();
        }
        for(int i=1;i<=m;i++){
            int x,y,z,a;
            scanf("%d%d%d%d",&x,&y,&z,&a);
            q[i]={x,y,z,a};
            am[i]=a;
            v[x].push_back(y);
            v[y].push_back(x);
            v[x].push_back(z);
            v[y].push_back(z);
        }
        sort(am+1,am+1+m);
        sort(q+1,q+1+m);
        dijkstra();
        f[m+1]=build(1,1,n,0);
        d[m+1]=build(1,1,n,1);
        rt[m+1]=build(1,1,n,2);
        for(int i=m;i>=1;i--){
            int x=q[i].u,y=q[i].v;
            add(x,y,i+1);
        }
        scanf("%d%d%d",&Q,&k,&s);
        int lst=0;
        while(Q--){
            int x,y;
            scanf("%d%d",&x,&y);
            x=(x+lst*k-1)%n+1;
            y=(y+lst*k)%(s+1);
            int t=upper_bound(am+1,am+1+m,y)-am;
            int F=getf(t,x);
            lst=query(rt[t],1,n,F);
            printf("%d\n",lst);
        }
    }
    return 0;
}