期望得分： (0+40+0 = 40)
实际得分：(0+40+0=40)
毒瘤出题人把每道题的算法都写在了标题上，但就是不会做。
(T1) 考试的时候题意都没有理解透彻，想打暴力却不知道如何下手。
(T2) 暴力 (for) 循环都有 (80) 分，自己的大常数做法跑的比暴力还慢。
(T3) 不说了，连题都读不懂。
这两天好像都考到了李超线段树，但是我没怎么接触过，考完之后去恶补了一下。
T1多项式 poly
题意描述
给你一个 (n) 维的多面体，定义它的面是一个 (n-1) 维多面体，已知它必定有 (2n) 面。
我们把这个 (n) 维体的所有面都染色。
现在，给你这个多面体每一维的长度，然后可以将这个 (n) 维体划分成 (displaystyle prod_{i=1}^{n} a_i) 个每个边的边长为 (1) 的小 (n) 维体。
定义一个小 (n) 维体的权值是它有多少个面被染色。
输出每个权值的小 (n) 维体的个数，显然可以知道，权值范围在 ([0,2n)) 中，所以只需要把 ([0,2n)) 的所有答案都输出即可。
答案对 (469762049) 取模。
数据范围： (nleq 10^5, a_ileq 469762049)
solution
题解的做法是找递推式，然后用 分治 (NTT) 优化这个递推过程。
不理解题意的菜鸡溜了溜了。
T2 数据结构 data_struct
题意描述
有 (n) 个 (y = kx+b) 形式的方程，有 (m) 次操作，操作分为三种类型：
- 操作1：给定 (l,r,x) 求将 (x) 带入 (l,r) 中的方程的最大值。
- 操作2：给定 (p,v) 将 (k_p) 增加 (v) 。
- 操作3：给定 (l,r,v) 将 $b_l....b_r $ 增加 (v) 。
数据范围：(1leq xleq 1000, 1leq vleq 1000, k_ileq 1000,b_ileq 10^6,nleq 2 imes 10^5,mleq 2 imes 10^6)
其中操作 (1) 的数量和操作 (3) 的数量和不超过 (10^5)
solution
分块套李超线段树。
如果没有操作 (3) 的话，这道题就是个李超线段树的板子。
但有了操作 (3) 我们很难维护出操作后的优势线段。
考虑用分块套李超线段树来解决这个问题，具体来说就是：
我们把序列划分为 (sqrt{n}) 个块，对于每个块都建一棵李超线段树。
对于操作 (1) ,散块的话我们直接暴力扫一遍，对于整块，我们在其对应的李超线段树里面查询一下即可。
对于操作 (2), 斜率增大后的直线肯定比原来的直线更优，所以我们直接把新直线插入到对应块的李超线段树即可。
对于操作 (3), 散块的话我们还是暴力扫一遍，把新的直线插入到对应块的李超线段树当中。对于整块，相当于是把块内的所有直线都向上平移了一段距离，优势线段不会改变，直接打个标记即可。
不知道为什么我的代码跑的贼慢，卡了卡常才勉强过去。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,m,maxn,block,opt,l,r,v,tot,x;
int pos[N],L[1010],R[1010],k[N],b[N],tag[1010],s[5000010],rt[1010];
struct node
{
int lc,rc;
int pl,pr;
}tr[5000010];
#define l(o) tr[o].pl
#define r(o) tr[o].pr
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
return s * w;
}
int calc(int id,int x)
{
return k[id] * x + b[id];
}
void build(int &o,int L,int R)
{
o = ++tot;
l(o) = L, r(o) = R;
if(L == R) return;
int mid = (L + R)>>1;
build(tr[o].lc,L,mid);
build(tr[o].rc,mid+1,R);
}
void insert(int o,int l,int r,int u)
{
if(l <= l(o) && r >= r(o))
{
int mid = (l(o)+r(o))>>1, v = s[o];
int t1 = calc(u,mid), t2 = calc(v,mid);
if(!s[o]) {s[o] = u; return;}
if(l(o) == r(o))
{
if(t1 > t2) s[o] = u;
return;
}
if(k[u] > k[v])
{
if(t1 > t2) s[o] = u, insert(tr[o].lc,l,mid,v);
else insert(tr[o].rc,mid+1,r,u);
}
else if(k[u] < k[v])
{
if(t1 > t2) s[o] = u, insert(tr[o].rc,mid+1,r,v);
else insert(tr[o].lc,l,mid,u);
}
else if(b[u] > b[v]) s[o] = u;
}
else
{
int mid = (l(o)+r(o))>>1;
if(l <= mid) insert(tr[o].lc,l,mid,u);
if(r > mid) insert(tr[o].rc,mid+1,r,u);
}
}
int query(int o,int l,int r,int x)
{
int res = calc(s[o],x);
if(l(o) == r(o)) return res;
int mid = (l(o)+r(o))>>1;
if(x <= mid) res = max(res,query(tr[o].lc,l,mid,x));
else res = max(res,query(tr[o].rc,mid+1,r,x));
return res;
}
void modify(int x,int y,int v)
{
if(pos[x] == pos[y])
{
for(int i = x; i <= y; i++) b[i] += v, insert(rt[pos[x]],1,1000,i);
}
else
{
int px = pos[x], py = pos[y];
for(int i = x; i <= R[px]; i++) b[i] += v, insert(rt[px],1,1000,i);
for(int i = px+1; i <= py-1; i++) tag[i] += v;
for(int i = L[py]; i <= y; i++) b[i] += v, insert(rt[py],1,1000,i);
}
}
int query(int x,int y,int v)
{
int res = 0;
int px = pos[x], py = pos[y];
if(px == py)
{
for(int i = x; i <= y; i++) res = max(res,k[i]*v+b[i]+tag[px]);
return res;
}
else
{
for(int i = x; i <= R[px]; i++) res = max(res,k[i]*v+b[i]+tag[px]);
for(int i = px+1; i <= py-1; i++) res = max(res,query(rt[i],1,1000,v)+tag[i]);
for(int i = L[py]; i <= y; i++) res = max(res,k[i]*v+b[i]+tag[py]);
return res;
}
}
signed main()
{
freopen("data_struct.in","r",stdin);
freopen("data_struct.out","w",stdout);
n = read(); m = read(); block = pow(n,0.59);
for(int i = 1; i <= n; i++) k[i] = read();
for(int i = 1; i <= n; i++) b[i] = read();
for(int i = 1; i <= n; i++)
{
pos[i] = (i-1)/block+1;
L[pos[i]] = n+1;
maxn = max(maxn,pos[i]);
}
for(int i = 1; i <= n; i++)
{
L[pos[i]] = min(L[pos[i]],i);
R[pos[i]] = max(R[pos[i]],i);
}
for(int i = 1; i <= maxn; i++) build(rt[i],1,1000);
for(int i = 1; i <= n; i++) insert(rt[pos[i]],1,1000,i);
for(int i = 1; i <= m; i++)
{
opt = read();
if(opt == 1)
{
l = read(); r = read(); x = read();
printf("%lld
",query(l,r,x));
}
if(opt == 2)
{
l = read(); v = read();
k[l] += v;
insert(rt[pos[l]],1,1000,l);
}
if(opt == 3)
{
l = read(); r = read(); v = read();
modify(l,r,v);
}
}
fclose(stdin); fclose(stdout);
return 0;
}
T3 动态规划 dp
题意描述
从上次打完最后的副本之后，(QAQ) 她决心想要出一个有价值的题，然后就有了这道题。现在，她想给小朋友们发糖（大雾），她现在有 (n) 个薛定谔的糖果盒，她可以进行 (m) 次如下的三个操作
- +1s
- 选出 (k) 个糖果盒，每个糖果盒有 (P\%) 的概率开出糖果。（可以包含已经打开的糖果盒，由于每个糖果盒是量子态的，所以可能之前有糖果的糖果盒这次扣上盒盖的后，可能会变成一个空盒）
- 选出来 (T) 个礼品盒，第 (i) 个糖果盒有 (min(P+i-1,100)\%) 的概率开出糖果
现在 (QAQ) 想要知道，她期望最多能拿出多少个糖果。
结果保留 (5) 位小数。
数据范围：(Pleq 100,Tleq 20,Nleq 500,Mleq 500)
solution
咕咕咕