搞颓记录

8-1

考了自己的题,结果T1锅了

T1 CF原题数据太水,导致我的假做法也能过

不过问题不太大,修改了一下就过了

8-2

Process

T1搞了一个小时,后面在想T2的20分怎么做,以及T3的正解做法,均无果

Score

100 + 10 + 30 = 140

T1

每个点维护一个二进制标记,如果第ii位为11,则表示它子树内深度为ii的点需要翻转左右儿子

修改的时候,因为至多只有首尾两层是不满的段,其他中间的段都是满的,因此中间的每次都是O(1)O(1)的,于是总复杂度是O(nlogn)O(n\log n)

修改不满的段的时候的做法比较巧妙,但也不难想,以后如果忘了看看代码就懂了。。。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = (1 << 20) + 100;

int N, M, Q;
int pw2[30];

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
struct info
{
int val, tag;
} node[Maxn << 2];

inline void build (int o, int l, int r)
{
if (l == r) node[o].val = l;
else build (lson), build (rson);
}

inline void update (int o, int l, int r, int d, int x, int y, int z, int tag_now)
{
// cout << x << ' ' << y << endl;
if (x <= l && r <= y) { node[o].tag ^= pw2[z]; return ; }

tag_now ^= node[o].tag;
if (!(tag_now & pw2[d]))
{
if (x <= mid) update (lson, d + 1, x, y, z, tag_now);
if (y > mid) update (rson, d + 1, x, y, z, tag_now);
}
else
{
if (x <= mid) update (rs, l, mid, d + 1, x, y, z, tag_now);
if (y > mid) update (ls, mid + 1, r, d + 1, x, y, z, tag_now);
}
}

inline int query (int o, int l, int r, int d, int x, int tag_now)
{
if (l == r) return node[o].val;

tag_now ^= node[o].tag;
// DEBUG (o);
// cout << tag_now << endl;
if (!(tag_now & pw2[d]))
{
if (x <= mid) return query (lson, d + 1, x, tag_now);
return query (rson, d + 1, x, tag_now);
}
else
{
if (x <= mid) return query (rs, l, mid, d + 1, x, tag_now);
return query (ls, mid + 1, r, d + 1, x, tag_now);
}
}

#undef mid
}

inline int cross (int l, int r, int x, int y)
{
if (x <= l)
{
if (y >= l) return 1;
return 0;
}
else
{
if (x <= r) return 1;
return 0;
}
}

inline void Solve ()
{
pw2[0] = 1;
for (int i = 1; i <= N; ++i) pw2[i] = pw2[i - 1] * 2;
SEG :: build (1, 1, M);

while (Q--)
{
int op = read<int>();
if (op == 1)
{
int l = read<int>(), r = read<int>();
for (int i = 0; i < N; ++i)
if (cross (l, r, pw2[i], pw2[i + 1] - 1))
SEG :: update (1, 1, pw2[i], 0, max (l, pw2[i]) - (pw2[i] - 1), min (r, pw2[i + 1] - 1) - (pw2[i] - 1), i, 0);
}
else printf("%d\n", SEG :: query (1, 1, M, 0, read<int>(), 0));
}
}

inline void Input ()
{
N = read<int>(), Q = read<int>();
M = 1 << N;
}

int main()
{

freopen("tree.in", "r", stdin);
freopen("tree.out", "w", stdout);

Input ();
Solve ();

return 0;
}

T2

还没改,不知道会不会改

T3

一个经典套路:忽略题意中的走的顺序,从左往右依次加点进行dp

那么原序列就会被分成若干个联通块(实际上是若干条链,这里暂且称作联通块),设dp[i][j]dp[i][j]为考虑到第ii个点,有jj个联通块的方案数,具体转移见代码

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
inline int left (int x) { if (A[x] != 'R') return 1; return 0; }
inline int right (int x) { if (A[x] != 'L') return 1; return 0; }

// 这里的联通块是指一条链(方向不定,反正展开就是一条链)
// 需要保证每个联通块的末尾为R(因为前面的已经考虑过了,如果还剩了L就连不起来了)
// 普通联通块: 除了S所在联通块和T所在联通块,其他的联通块

// 每种点的作用:
// 能往左走: 连接前面两个联通块的桥梁; 作为某个联通块的开头
// 能往右走: 单独作为一个联通块; 作为某个联通块的结尾

inline void Solve ()
{
memset(Dp, 0, sizeof Dp);
if (A[N] == 'R' && T != N) { puts("0"); return ; }
Dp[N][0] = 1;
for (int x = N - 1; x >= 1; --x)
{
for (int k = 0; k <= N; ++k)
{
int &ans = Dp[x][k];
if (x == S)
{
if (k && left (x)) Add (ans, (LL) k * Dp[x + 1][k - 1] % Mod);
if (right (x)) Add (ans, Dp[x + 1][k]);
}
else if (x == T)
{
if (k) Add (ans, (LL) k * Dp[x + 1][k - 1] % Mod);
Add (ans, Dp[x + 1][k]);
}
else
{
if (left (x))
{
if (k >= 2) Add (ans, (LL) k * (k - 1) % Mod * Dp[x + 1][k - 1] % Mod); // 连接两个普通联通块
if (k && x > S) Add (ans, (LL) k * Dp[x + 1][k - 1] % Mod); // 连接普通联通块和首联通块
if (x > T)
{
if (k) Add (ans, (LL) k * Dp[x + 1][k - 1] % Mod); // 连接普通联通块和尾联通块
Add (ans, Dp[x + 1][k]); // 放在尾联通块的开头
}

Add (ans, (LL) k * Dp[x + 1][k] % Mod); // 放在普通联通块的开头
}
if (right (x))
{
Add (ans, Dp[x + 1][k + 1]); // 单独作为一个联通块
if (x > S) Add (ans, Dp[x + 1][k]); // 放在首联通块的末尾
Add (ans, (LL) k * Dp[x + 1][k] % Mod); // 放在普通联通块的末尾
}
}
}
}

printf("%d\n", Dp[1][0]);
}

8-3

上午听zjm讲组合,生成函数,多项式;下午听zqc讲容斥反演

似乎迷迷糊糊听懂了一点,可是理解还是不够

8-4

Process

cxr的题,T1傻逼题居然没想到,自闭了自闭了

就写了T1 T3两个暴力,根本没开T2,后来改题的时候看T2发现好像也不太难

60 + 0 + 60 = 120

T1

真的是sb题

考虑把答案设为根,此时会有一些限制不满足,又因为一定在根的子树中,那么设did_i表示第ii个限制至少需要深度did_i才满足限制,找到最大的did_i,以及其对应的点xx,判断xx是否合法即可

T2

题解很清楚

第二部分中,我们假设所有在AA集合中的数都取到了最大值,显然它们还在AA集合中,但相对位置可能会变化,不过对统计方案数并没有影响。

第二部分中xx实际上还与AA有关,即cnt1+x+1Acnt1 + x + 1 \le A,因此不能直接把x(cnt2x)(cnt1B1x)\sum_{x}\binom{cnt2}{x}\binom{cnt1}{B-1-x}利用范德蒙德卷积变成(cnt1+cnt2B1)\binom{cnt1 + cnt2}{B-1}

T3

没改

8-5

Process

T3模板题, T1花了点时间推式子,T2傻逼dp居然都没想到(最后时间不太够,有点急)

100 + 30 + 100 = 230

T1

a,b,c,da, b, c, d分别为(0,0),(0,1),(1,0),(1,1)(0, 0), (0, 1), (1, 0), (1, 1)的数量

a1,b1,c1,d1a_1, b_1, c_1, d_1分别为这些状态在答案的左边的数量,a2,b2,c2,d2a_2, b_2, c_2, d_2为右边

可以列出一些方程,手解一下就行

最后化出来一步b1+c1=tb_1 + c_1 = t,那么取b1=min{b,t}b_1 = \min\{b, t\},看c1c_1是否合法即可

T2

dp[i]dp[i]表示取到第ii个物品的答案,把与第几个箱子有关那个部分的贡献拆到后面去,即有转移:

dp[i]=minj{dp[j]+maxk=j+1i}+j=i+1nwj dp[i] = \min_{j}\{dp[j] + \max_{k=j + 1}^{i}\} + \sum_{j=i + 1}^{n}w_j

单调栈 + 线段树维护一下max\max部分即可

类似于19-6-22 T1

T3

混合图欧拉回路模板题

19-8-5-1


今天晚上想搞一点zjm课件的题

8-6

讲课,拖堂了1个小时

讲得有点累,幸好把话筒修好了,不然可能会当场去世

晚上把zjm的组合题搞完了

8-7

Process

今天整个不在状态。一个sbT2还想了一两个小时。

T1想了个乱搞,没搞出来。T3没怎么仔细想,结果爆零了

最后T2还因为没卡常爆成40

10 + 40 +0 = 50

T1

枚举每个点作为起点搜索 , 设 dp[i][j][k]dp[i][j][k] 为到 (i,j)(i,j) 吃到豆子的状态为 kk 的最大得分 .

如何记录是否吃到了某个豆子呢 ?

当蛇在豆子的右边穿过奇数次时就能包围住 , 穿过偶数次就没有包围住.

预处理一下经过某个点后,豆子是否被选中这个状态如何改变即可

T2

二分答案,差分check

这里必须要加一个优化:不要每次都从1到mid去算答案,而是类似于一个指针在上面移动,维护上次check到这次check中间的变化量

T3

不难发现,每行填的数都是一个排列去掉一个数

枚举这个断点即可得到O(n3)O(n^3)的暴力,稍微优化一下就变成O(n2)O(n^2)

dp[i][j]dp[i][j]表示第ii行,断点在jj的答案,则:

dp[i][j]=dp[i1][j+1]+dp[i][j1] dp[i][j] = dp[i - 1][j + 1] + dp[i][j - 1]

结合这里的图可以发现,答案就是从原点出发,只能向右或向上走,不接触直线A,B,到达点(n+m+1,n)(n+m+1,n)的路径条数

考虑容斥,先算从原点到(n+m+1,n)(n + m + 1, n)的总方案数,减去碰到A,BA, B的方案数

考虑将终点pp关于AA对称得到pp',发现从原点到pp'的方案数就是碰到A至少一次的方案数

同理,关于BB对称后的答案是碰到B至少一次的方案数

显然这样又会算重,算重的情况是先碰到A,然后碰到B,或者先碰到B,然后碰到A

抽象一下就是碰到边界的序列中存在ABBA子序列的方案

于是又可以继续对称,把终点先关于BB对称,再关于AA对称,即算出了存在子序列AB的方案

以此类推

不难发现容斥系数为(1)cnt(-1)^{cnt}cntcnt表示对称的次数


模拟求解即可,对称到不在第一象限时就停止。最多对称log\log

8-8

Process

T1花了半个小时,然后一直在搞T2。T2完全没有想到分治,一直在往扫描线的方向去想,始终无果

T1

GC's Blog)

T2

统计序列中点对的问题要往分治上想!!!

考虑跨区间的贡献!!!

想到分治后不难

题解写得还可以

T3

最后需要找到一个tt,使得i=1n__builtin_popcount(t+mxa[i])\sum_{i=1}^{n}\_\_builtin\_popcount(t + mx - a[i])最小

可以考虑tt在每一位上的取值(0/1),然后dp

暴力dp需要知道当前位往下一位有哪些数进了位

但是不难发现,若一个数前i1i-1位对应的数越大,它在第ii位越容易进位

那么根据这个性质每次将数排序后,进位的数就是一段前缀了

具体细节可见Sol/Code

8-9

上午xz讲数据结构,下午jwb讲线段树

今天有点晕,不想接受新的东西。。。就水过去了

有时间搞下jwb的课件

8-10

Process

开场想了下T1,无果。然后发现T2很sb,写完之后去看T3,发现一个很直观很暴力的线段树合并做法。

T3调到考试结束前半个小时,最后慌慌张张写T1暴力,结果部分分写挂了

最后T2也挂了20分。。。

35 + 80 + 100 = 215

T1

转化为求多少点对之间存在至少dd条不相交路径

  • 若联通:至少1条
  • 若在同一个边双中:至少2条
  • 若把图中任意一条边删除后,它们仍在同一边双中:3条

第三种情况枚举删哪条边即可

T2

转化为求 (x,y)(x, y)对数,其中ylyl表示yy的位数

枚举xx,再枚举ylyl,用个mapmap随便数下有多少个yy即可

T3

我的暴力线段树合并做法:

对于一个询问x,kx, k来说,它要找xx子树内,边权前缀maxk\max\le k的点的个数(这里的前缀意思是它到xx的这一段路径)

维护一个权值线段树,下标是边权离散化之后的值,权值是每个边权对应的答案和

显然子树的限制可以通过线段树合并来解决

而对于一条权值为dd的边来说,它子树内所有d\le d的边都要变成dd(因为是前缀max\max

直接在线段树上区间查,区间置00(把点直接删掉)即可


晚上搞了TJOI2015旅游和xsy1599A

8-11

Process

倒序做题,T1写了个斜率优化(差不多又快忘光了。。。)

50 + 100 + 100 = 250

T1

有一个性质没挖掘出来:

  • 若钦定某个点在最优策略里被选,那么策略与它的值没有关系

剩下的看sol吧

用分治优化dp,同时用上斜率优化

T2

贪心最小生成树

每个点只往它当前这一列的相邻点,以及另一列理它最近的两个点连边即可

T3

随便dp一下,处理出每个点到根的最短路


晚上把AGC028D搞完了,然后发现斜率优化学得狗屎样的,重新学了下

8-12

上午的贪心好神啊。。。

下午图论听了一部分

今天的课件都要找时间搞了

晚上搞了NOI2019D1T1和「LNOI2014」LCA

8-13

Process

前两题搞完的时候是10:40,太慢了。。。T2写了半天

T3写了个暴力,搞链的分但是做法有点问题

T1

题解很清楚

我直接找的规律,规律很好找

T2

我的做法和kk有关,对每个点直接枚举其对应的kk的具体的值,剩下的条件随便维护下即可

也可以CDQ分治,做到与kk无关

T3

aabb的链上dp,设dp[i][j]dp[i][j]表示考虑到链上第ii个点,它在操作序列中位于第jj个位置

每次把点往前面的方案里插即可

对组合数的理解的应用还要再深一点

8-14

Process

想了一上午T1,不会做,期间想了一个假做法,以及推了下T2的式子,太麻烦就弃了

于是爆零了

0 + 0 + 0 = 0

T1

离散化之后就可以考虑每个单位格子对答案的贡献!!!

怎么这么sb都想不到

我想的做法是n2n^2枚举两个点,以它们形成的矩形去算贡献,但是会有细节问题

考虑单位格子的话就不存在各种奇奇怪怪的问题了!!!

T2

做法来自xcy

考虑[L,R][L, R]中的每个点对答案的贡献,发现是wiE(i)w_i * E(i)E(i)E(i)表示ii这个点期望要走多少次

a=j=iRpj\displaystyle a = \prod_{j=i}^{R}p_j,那么有

E(i)=a+2×(1a)a+3×(1a)2a+...=k=0(k+1)(1a)ka=1a \begin{aligned} E(i) &= a + 2 \times(1-a)\cdot a + 3\times (1-a)^2 \cdot a + ...\\ &=\sum_{k=0}^{\infty}(k + 1)(1-a)^ka\\ &=\frac{1}{a} \end{aligned}

于是答案就是i=LRwij=iRpj\displaystyle \sum_{i=L}^{R}\frac{w_i}{\prod_{j=i}^{R}p_j}

线段树每个结点维护一下wij=iRpj\displaystyle \frac{w_i}{\prod_{j=i}^{R}p_j}j=iRpj\displaystyle {\prod_{j=i}^{R}p_j}即可

最后把nn开到2的幂次,预处理出修改需要的值即可

T3

思路:

对每种权值维护一棵树,每个结点有黑白两种颜色,白色表示这个点是当前这种权值,黑色表示不是

那么答案就是所有操作之后,每个黑色联通块的size2size^2的和

LCT维护即可

计算答案的时候先初始化一个全是黑点的树,离线处理每个颜色,处理完一个颜色反着改回去

类似于CDQ分治时清空BIT的方法

具体实现见,或出题人sol

8-15

神仙讲课

晚上搞了两道gc的课件

8-16

Process

刚了一上午的T2

60 + 100 + 20 = 180

T1

求整数分拆的方案数

先考虑两种dp

f[i][j]f[i][j] : 大小为ii的数,用不超过jj的数拆分的方案数

转移考虑是否加上一个权值为jj的数

g[i][j]g[i][j] : 大小为ii的数,用jj个数拆分的方案数

转移考虑把当前所有数+1+1,或者新加一个值为11的数

注意到,ff的第二维只与权值大小有关,gg的第二维只与个数有关

又因为权值大于n\sqrt n的数不会超过n\sqrt n个,于是可以考虑把ffgg的第二维都只枚举到n\sqrt n

这里要把gg的定义稍微改一下,要保证这jj个数都>n> \sqrt n

m=nm = \sqrt n,则答案长这样

ans=i=0n(j=0mg[i][j])×f[ni][m] ans = \sum_{i=0}^{n}\Big(\sum_{j=0}^{m}g[i][j]\Big) \times f[n - i][m]

T2

定义计算括号序列为将((看成+1+1))看成1-1,求前缀和

我的做法比较暴力

首先考虑把所有??先看成((,计算括号序列的值,设其为aa数组

若某个合法的括号序列以ii为左端点,则右端点jj需要满足,从ii开始走到jj的过程中,括号序列的值非负

形式化地说,需要满足mink=ijajai10\displaystyle \min_{k = i}^{j}a_j - a_{i - 1} \ge 0

显然,这个式子具有单调性,即合法的右端点一定在区间[i,Ri][i, R_i]中,可以二分求出RiR_i


同理,把??看成)),计算后缀括号序列后,也能类似地求出LiL_i,表示以ii为右端点时,左端点一定在区间[Li,i][L_i, i]

一个小结论:只要满足[i,Ri][i, R_i][Li,i][L_i, i]这两个限制,就一定能构造出合法地括号序列

考虑枚举右端点ii,那么就是要找有多少个左端点j[Li,i]j\in[L_i, i],满足RjiR_j \ge i

这个随便用个数据结构维护一下即可

T3

19-8-16-1

8-17

gc的题,我验的题

T1

补集转化,然后用隔板法算下方案数即可

T2

先处理出关于cic_i递减的单调栈

viv_i排序,从小到大考虑,在单调栈上二分找到恰好能卖的那个位置

从那个位置开始把一段前缀减掉,用线段树维护即可

T3

把点权拆到边权上,每次考虑一个点把之前的哪个点作为父亲最优

显然只要考虑它到原树的根的那条链上的点即可,因为其他点都不会更优


晚上打了百度之星初赛

T2贪心没搞出来,没进250。。。

8-18

上午csy讲字符串,有一两道题断了

下午xcy讲树,基本还在线

晚上打了百度之星初赛第二场

抄了GC的T4,最后排名77

8-19

Process

似乎现在在考的是去年纪中的题了

T1还没想清楚细节就开始码,导致浪费了很多时间,最后只能交个log2\log^2的暴力草草收场

T2考过很多次了,结果遇到的时候还话了不少时间才看出来是那个模型。。。

T3没时间了,暴力没调出来(实际上是看漏了个条件)

Summary

现在开始的模考一定要认真对待!!!

每道题先写好暴力,想正解/码正解的题一定要掐好时间,不能出现暴力分没写完,甚至是有题爆零的情况!!!

T1

改了个好多细节的做法

二分某一个数组的下标,那么可以计算出另外一个数组期望的下标

再通过判断两个数组某些位置上的值的大小关系判断往左还是往右走

T2

dp[i]=maxj=0i1dp[j]+f(mink=j+1iak) dp[i] = \max_{j=0}^{i-1}dp[j] + f(\min _{k=j+1}^{i}a_k)

这天一模一样

T3

首先有一个式子:对于一个随机变量xx,其期望值为E(x)=i=1P(xi)\displaystyle E(x)= \sum_{i=1}^{\infty}P(x\ge i)

根据期望的线性性把式子拆开,考虑每个比xx小的ii对答案的贡献

接下来对每个询问[l,r][l, r],考虑每个xx的贡献:

19-8-19-1

也就是说,我们只需要求出[l,r][l, r]内每个位置的最小值x\ge x的概率(P(vix))\big(P(v_i\ge x)\big)

它就是小于xx的数不选的概率的乘积,减去所有数都不选的概率


然后考虑xx在变化的时候,答案如何变化(假设从yy变为xx

显然,最外面的1-可以最后计算,于是可以只考虑i=lr1P(vix)\displaystyle \prod_{i=l}^{r}1 - P(v_i\ge x)的变化,那么直接除掉1P(viy)1 - P(v_i\ge y),再乘上1P(vix)1 - P(v_i\ge x)即可

但是这样做当P(vix)=1P(v_i\ge x) = 1时会有问题,不过因为P(vix)P(v_i \ge x)是随xx的变大而递减的

即若x>y,P(vix)=1\exists x> y, P(v_i\ge x) = 1,那么P(viy)=1P(v_i\ge y) = 1

所以从大到小枚举xx就行了


最后考虑多组询问如何处理

因为所给区间互不包含,所以每个点被包含的区间也是一个区间

只需要把答案的这段区间直接乘上当前的贡献,线段树维护即可

看代码可能更好理解。。。

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 2e5 + 100;
const int Mod = 1e9 + 7;

namespace MATH
{
inline void Add (int &a, int b) { if ((a += b) >= Mod) a -= Mod; }

inline int Pow (int a, int b)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
return ans;
}
}

using namespace MATH;

int N, M, Q;
struct info
{
int x, y, p;
} A[Maxn];
pii B[Maxn];

stack <int> stk[Maxn];
int base[Maxn];
int L[Maxn], R[Maxn];

inline int cmp (info a, info b) { return a.y < b.y; }

inline int cmp_x (pii a, pii b) { return a.x < b.x; }

inline int cmp_y (pii a, pii b) { return a.y < b.y; }

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r
struct info
{
int sum, tag;
info () { sum = 0, tag = 1; }
} node[Maxn << 2];

inline void push_up (int o) { node[o].sum = (node[ls].sum + node[rs].sum) % Mod; }

inline void push_down (int o)
{
if (node[o].tag == 1) return ;
node[ls].sum = (LL) node[ls].sum * node[o].tag % Mod;
node[rs].sum = (LL) node[rs].sum * node[o].tag % Mod;
node[ls].tag = (LL) node[ls].tag * node[o].tag % Mod;
node[rs].tag = (LL) node[rs].tag * node[o].tag % Mod;
node[o].tag = 1;
}

inline void build (int o, int l, int r)
{
if (l == r) return void (node[o].sum = 1);
build (lson), build (rson);
push_up (o);
}

inline void update (int o, int l, int r, int x, int y, int val)
{
if (x > y) return ;
if (x <= l && r <= y)
{
node[o].sum = (LL) node[o].sum * val % Mod;
node[o].tag = (LL) node[o].tag * val % Mod;
return ;
}
push_down (o);
if (x <= mid) update (lson, x, y, val);
if (y > mid) update (rson, x, y, val);
push_up (o);
}

inline int query () { return node[1].sum; }
#undef mid
}

inline void Calc (int x)
{
int pre = 1 - (stk[x].top() - base[x]) % Mod + Mod;
stk[x].pop();
int now = 1 - (stk[x].top() - base[x]) % Mod + Mod;
SEG :: update (1, 1, Q, L[x], R[x], (LL) now * Pow (pre, Mod - 2) % Mod);
}

inline void Init ()
{
sort (A + 1, A + M + 1, cmp);
for (int i = 1; i <= N; ++i) stk[i].push (1);
for (int i = 1; i <= M; ++i)
{
int res = stk[A[i].x].top();
stk[A[i].x].push ((LL) res * (1 - A[i].p + Mod) % Mod);
}
for (int i = 1; i <= N; ++i) base[i] = stk[i].top();

sort (B + 1, B + Q + 1);
for (int i = 1; i <= N; ++i)
{
L[i] = lower_bound (B + 1, B + Q + 1, mp (0, i), cmp_y) - B;
R[i] = upper_bound (B + 1, B + Q + 1, mp (i, 0), cmp_x) - B - 1;
}

SEG :: build (1, 1, Q);
}

inline void Solve ()
{
Init ();

int ans = 0, i = M;
while (i)
{
int j = i;
while (A[j].y == A[i].y && j >= 1) Calc (A[j].x), --j;
Add (ans, (LL) SEG :: query () * (A[i].y - A[j].y) % Mod);
i = j;
}

ans = ((LL) Q * A[M].y % Mod - ans + Mod) % Mod;
cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), M = read<int>(), Q = read<int>();
for (int i = 1; i <= M; ++i)
A[i].x = read<int>(), A[i].y = read<int>(), A[i].p = read<int>();
for (int i = 1; i <= Q; ++i) B[i].x = read<int>(), B[i].y = read<int>();
}

int main()
{

freopen("max.in", "r", stdin);
freopen("max.out", "w", stdout);

Input ();
Solve ();

return 0;
}

```

8-20

Process

又看错题。。。T2算方案数的时候看成当且仅当aia_i不同,死活不会算

T1想错了一个地方,以为mm只会到10610^6。。。

T3比较简单,直接矩阵快速幂即可

T1

显然对于相同体积的物品只用留权值最大的

暴力是O(100m)O(100m),考虑mm比较大的时候直接取性价比最高的,当mm10610^6左右的时候再dp

T2

第一问用后半部分减去前半部分

第二问奇偶部分相减

第三问括号序列,直接卡特兰数

T3

暴力容斥,然后矩阵快速幂算方案数