马上就下半年的区域赛了，应该是最后几场了。这里系统的而复习一下数据结构吧。
（先占坑，打cf去了）
（啊难死了***E题怎么比D题还简单啊啊啊没写完）
1.虚树
首先，虚树用于解决一类特殊的树形dp问题（目前遇见的是这样） 类似于，每次询问给你一个树的子集，在这个子集做dp 虚树实现的功能就是每次询问的时候，单独拿出“有用的点”建树 然后就是些一般的树形dp了 具体的，有用的点包括询问点和他们的lca 然后详细的讲解过程就不写了，挂一个学弟的博客吧
建树的复杂度是O(k)的，具体是O(2*k),然后还要加上每次每次dp的复杂度
简单练习题 [Gym-100889J]
每次询问k个点中每个点到其他点（k个中）的最远距离 如果是简单的k个点的dp的话，dp[i][0]/[1]分别表示i往上往下的max距离
dp[i][0]=max{dp[v][0]+dis(i,v)}
dp[i][1]=max{dp[fa][1],dp[bro][0]}+dis[fa][i]}
这里多次询问且有修改，如果每次可以建立好虚树就和上面一样了 对于修改，就是一个简单的按dfs序建线段树然后区间修改单点查询
#include<bits/stdc++.h>
#define ll long long
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
#define maxn 100010
using namespace std;
ll n, m, lef[maxn], rig[maxn], dis[maxn], dep[maxn], dp[maxn][2];
ll s[maxn * 4], laz[maxn * 4], topt, fa[maxn][30], pos[maxn];
ll top, stck[maxn];
struct edge {
ll v, t;
};
vector<edge> G[maxn];
vector<ll> P[maxn];
void Build(ll k, ll l, ll r) {
if (l == r) {
s[k] = dis[pos[l]];
return;
}
Build(lc, l, mid);
Build(rc, mid + 1, r);
s[k] = s[lc] + s[rc];
}
void Up(ll k, ll l, ll r) {
s[lc] += (mid - l + 1) * laz[k];
s[rc] += (r - mid) * laz[k];
laz[lc] += laz[k];
laz[rc] += laz[k];
laz[k] = 0;
}
void Insert(ll k, ll l, ll r, ll x, ll y, ll z) {
if (x <= l && y >= r) {
s[k] += (r - l + 1) * z;
laz[k] += z;
return;
}
if (laz[k])Up(k, l, r);
if (x <= mid)Insert(lc, l, mid, x, y, z);
if (y > mid)Insert(rc, mid + 1, r, x, y, z);
s[k] = s[lc] + s[rc];
}
ll Query(ll k, ll l, ll r, ll x) {
if (l == x && r == x)return s[k];
if (laz[k])Up(k, l, r);
if (x <= mid)return Query(lc, l, mid, x);
else return Query(rc, mid + 1, r, x);
}
void Dfs(ll now, ll from, ll deep, ll dist) {
lef[now] = ++topt;
pos[topt] = now;
dis[now] = dist;
dep[now] = deep;
fa[now][0] = from;
for (edge e:G[now]) {
if (e.v == from)continue;
Dfs(e.v, now, deep + 1, dist + e.t);
}
rig[now] = topt;
}
void Get_fa() {
for (ll j = 1; j <= 25; j++)
for (ll i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
ll LCA(ll x, ll y) {
if (dep[x] < dep[y])swap(x, y);
ll t = dep[x] - dep[y];
for (ll i = 0; i < 25; i++)
if (t & (1 << i))x = fa[x][i];
if (x == y)return x;
for (ll i = 25; i >= 0; i--)
if (fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
return fa[x][0];
}
void Add(ll p) {
if (top == 0) {
stck[++top] = p;
return;
}
ll lca = LCA(p, stck[top]);
if (lca == stck[top]) {
stck[++top] = p;
return;
}
while (top > 1 && lef[stck[top - 1]] >= lef[lca]) {
P[stck[top - 1]].push_back(stck[top]);
top--;
}
if (lca != stck[top]) {
P[lca].push_back(stck[top]);
stck[top] = lca;
}
stck[++top] = p;
}
struct node {
ll oo, o;
} a[maxn];
bool cmp1(node x, node y) {
return lef[x.oo] < lef[y.oo];
}
bool cmp2(node x, node y) {
return x.o < y.o;
}
void DP1(ll now) {
dp[now][0] = 0;
for (ll v:P[now]) {
DP1(v);
ll di = Query(1, 1, n, lef[v]) - Query(1, 1, n, lef[now]);
dp[now][0] = max(dp[now][0], dp[v][0] + di);
}
}
void DP2(ll now, ll fa) {
dp[now][1] = 0;
if (fa != 0) {
ll di = Query(1, 1, n, lef[now]) - Query(1, 1, n, lef[fa]);
dp[now][1] = dp[fa][1] + di;
for (ll v:P[fa]) {
ll dii = Query(1, 1, n, lef[v]) - Query(1, 1, n, lef[fa]);
if (v != now)dp[now][1] = max(dp[now][1], dp[v][0] + di + dii);
}
}
for (ll v:P[now])DP2(v, now);
P[now].clear();
}
int main() {
scanf("%lld", &n);
ll u, v, t, op, k;
for (ll i = 1; i < n; i++) {
scanf("%lld%lld%lld", &u, &v, &t);
G[u].push_back(edge{v, t});
G[v].push_back((edge{u, t}));
}
Dfs(1, 0, 1, 0);
Get_fa();
Build(1, 1, n);
scanf("%lld", &m);
while (m--) {
scanf("%lld", &op);
if (op == 1) {
scanf("%lld%lld%lld", &u, &v, &t);
for (edge &e:G[u])
if (e.v == v) {
if (dep[u] > dep[v])Insert(1, 1, n, lef[u], rig[u], t - e.t);
else Insert(1, 1, n, lef[v], rig[v], t - e.t);
e.t = t;
break;
}
} else {
scanf("%lld", &k);
top = 0;
for (ll i = 1; i <= k; i++) {
scanf("%lld", &a[i].oo);
a[i].o = i;
}
sort(a + 1, a + 1 + k, cmp1);
for (ll i = 1; i <= k; i++)Add(a[i].oo);
while (top > 1) {
P[stck[top - 1]].push_back(stck[top]);
top--;
}
sort(a + 1, a + 1 + k, cmp2);
DP1(stck[1]);
DP2(stck[1], 0);
for (ll i = 1; i <= k; i++)
printf("%lld ", max(dp[a[i].oo][0], dp[a[i].oo][1]));
printf("\n");
}
}
return 0;
}2.笛卡尔树
哇马上熄灯了，先占一个代码明天再说
笛卡尔树结构由Vuillmin在解决范围搜索的几何数据结构问题时提出的，从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。由此可知，笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。
笛卡尔树是一棵二叉树，树的每个节点有两个值，一个为key，一个为value。光看key的话，笛卡尔树是一棵二叉搜索树，每个节点的左子树的key都比它小，右子树都比它大；光看value的话，笛卡尔树有点类似堆，根节点的value是最小（或者最大）的，每个节点的value都比它的子树要大。
/*
2019牛客多校1 A
由题意 两颗笛卡尔树同构
*/
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
int n, a[maxn], b[maxn], s1[maxn], s2[maxn], top1, top2;
int fa1[maxn], fa2[maxn], lc1[maxn], lc2[maxn], rc1[maxn], rc2[maxn];
int main() {
while (~scanf("%d", &n)) {
top1 = top2 = 0;
int ans = n;
for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) {
while (top1 && a[s1[top1]] > a[i])
lc1[i] = s1[top1], top1--;
fa1[i] = s1[top1];
fa1[lc1[i]] = i;
if (fa1[i])rc1[fa1[i]] = i;
s1[++top1] = i;
while (top2 && b[s2[top2]] > b[i])
lc2[i] = s2[top2], top2--;
fa2[i] = s2[top2];
fa2[lc2[i]] = i;
if (fa2[i])rc2[fa2[i]] = i;
s2[++top2] = i;
if (top1 != top2) {
ans = i - 1;
break;
}
}
printf("%d\n", ans);
}
return 0;
}HDU 6305RMQ Similar Sequence
首先不难想到B序列构成的笛卡尔树和A长得一样，由于B序列是实数，我们就假设bi互不相同，然后对于任意一个序列，每个数期望为0.5，期望的和为0.5n，下面考虑这个序列合法的概率：1/Πsiz[i] siz为每个子树的大小，也就是 根节点rot是整个序列最大的 概率为1/n，rot.lc是1~rot.key-1里面最大的 概率为1/(rot.key-1)，其他同理
#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define maxn 1000010
using namespace std;
ll T, n, a[maxn], top, s[maxn], siz[maxn];
struct node {
ll fa, lc, rc;
} t[maxn];
ll Build() {
top = 0;
for (ll i = 1; i <= n; i++) {
ll k = top;
while (k && a[s[k]] < a[i])k--; //栈中比当前元素""的都出栈
if (k) { //find it，栈中元素没有完全出栈，当前元素为栈顶元素的右孩子
t[i].fa = s[k];
t[s[k]].rc = i;
}
if (k < top) { //出栈的元素为当前元素的左孩子
t[s[k + 1]].fa = i;
t[i].lc = s[k + 1];
}
s[++k] = i;//当前元素入栈
top = k;//top指向栈顶元素
}
t[s[1]].fa = 0;//遍历完成后的栈顶元素就是根
return s[1];
}
void Dfs(ll now) {
if (now == 0)return;
siz[now] = 1;
Dfs(t[now].lc);
Dfs(t[now].rc);
siz[now] += siz[t[now].lc] + siz[t[now].rc];
}
ll qc(ll x, ll y) {
ll res = 1;
while (y) {
if (y & 1)res = res * x % mod;
x = x * x % mod;
y >>= 1;
}
return res;
}
ll inv(ll x) {
return qc(x, mod - 2);
}
int main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
top = 0;
for (ll i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
t[i].fa = t[i].lc = t[i].rc = 0;
}
ll root = Build();
Dfs(root);
ll ans = n * inv(2) % mod;
for (ll i = 1; i <= n; i++)
ans = ans * inv(siz[i]) % mod;
printf("%lld\n", ans);
}
return 0;
}
/*
1
5
3 1 5 4 2
*/3.主席树
其实准备靠后一点再写主席树的，但是今天正好刷笛卡尔树的题用主席树给做了就一块写了
简单放一下代码吧
/*基础离散化+区间第k大*/
#include<cstdio>
#include<algorithm>
#define maxn 60010
#define mid (l+r)/2
using namespace std;
int n,m,num,a[maxn],A[maxn],s[maxn],lc[maxn],rc[maxn],r[maxn],cnt;
int init(){
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
int Build(int S,int L,int R){
cnt++;s[cnt]=S;
lc[cnt]=L;rc[cnt]=R;
return cnt;
}
void Insert(int &now,int pre,int l,int r,int k){
now=Build(s[pre]+1,lc[pre],rc[pre]);
if(l==r)return;
if(k<=mid)Insert(lc[now],lc[pre],l,mid,k);
else Insert(rc[now],rc[pre],mid+1,r,k);
}
int Query(int L,int R,int l,int r,int k){
if(l==r)return l;
int sum=s[lc[R]]-s[lc[L]];
if(sum>=k)return Query(lc[L],lc[R],l,mid,k);
else return Query(rc[L],rc[R],mid+1,r,k-sum);
}
int main()
{
n=init();m=init();
for(int i=1;i<=n;i++){
a[i]=init();A[i]=a[i];
}
sort(A+1,A+1+n);
num=unique(A+1,A+1+n)-A-1;
for(int i=1;i<=n;i++){
int pos=lower_bound(A+1,A+1+num,a[i])-A;
Insert(r[i],r[i-1],1,num,pos);
}
for(int i=1;i<=m;i++){
int L=init(),R=init();
int pos=(R-L)/2+1;
pos=Query(r[L-1],r[R],1,num,pos);
printf("%d\n",A[pos]);
}
return 0;
}然后是区间<=x的数有几个
这个题主席树的做法不难想 分治之后就是裸的主席树了，但是好像要两个log，而且我还是不知道这题为啥要用笛卡尔树（另外windows下手测他好像爆栈了，还特地去ubuntu跑了跑）
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
#define maxn 100010
using namespace std;
int n, m, a[maxn], A[maxn], s[maxn * 20], lc[maxn * 20], rc[maxn * 20], rot[maxn], cnt;
int mx[maxn][25], p[maxn];
ll ans;
void ST() {
for (int i = 1; i <= n; i++)
mx[i][0] = i;
for (int j = 1; j <= 20; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
if (a[mx[i][j - 1]] > a[mx[i + (1 << j - 1)][j - 1]])mx[i][j] = mx[i][j - 1];
else mx[i][j] = mx[i + (1 << j - 1)][j - 1];
for (int i = 0; i <= 20; i++)
if ((1 << i) <= n)p[1 << i] = i;
for (int i = 1; i <= n; i++)
if (!p[i])p[i] = p[i - 1];
}
int Query(int l, int r) {
int k = p[r - l + 1];
if (a[mx[l][k]] > a[mx[r - (1 << k) + 1][k]])return mx[l][k];
else return mx[r - (1 << k) + 1][k];
}
int Build(int S, int L, int R) {
cnt++;
s[cnt] = S;
lc[cnt] = L;
rc[cnt] = R;
return cnt;
}
void Insert(int &now, int pre, int l, int r, int k) {
now = Build(s[pre] + 1, lc[pre], rc[pre]);
if (l == r)return;
if (k <= mid)Insert(lc[now], lc[pre], l, mid, k);
else Insert(rc[now], rc[pre], mid + 1, r, k);
}
int Query(int L, int R, int x, int y, int l, int r) {
if(x>y)return 0;
if (x <= l && y >= r)return s[R] - s[L];
int res = 0;
if (x <= mid)res += Query(lc[L], lc[R], x, y, l, mid);
if (y > mid)res += Query(rc[L], rc[R], x, y, mid + 1, r);
return res;
}
int Ask(int l, int r, int x) {
if (l > r)return 0;
// printf("%d %d %d\n",l,r,x);
int pos = upper_bound(A + 1, A + 1 + m, x) - A - 1;
return Query(rot[l - 1], rot[r], 1, pos, 1, m);
}
void Dfs(int l, int r) {
int pos = Query(l, r);
if (pos - l < r - pos) {
for (int i = l; i <= pos; i++)
ans += Ask(pos, r, a[pos] / a[i]);
} else {
for (int i = pos; i <= r; i++)
ans += Ask(l, pos, a[pos] / a[i]);
}
if (l <= pos - 1)Dfs(l, pos - 1);
if (pos + 1 <= r)Dfs(pos + 1, r);
}
int main() {
// n=100000;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
// a[i]=rand()+1;
// a[i]=i;
A[i] = a[i];
}
ST();
sort(A + 1, A + 1 + n);
m = unique(A + 1, A + 1 + n) - A - 1;
for (int i = 1; i <= n; i++) {
int pos = lower_bound(A + 1, A + 1 + m, a[i]) - A;
Insert(rot[i], rot[i - 1], 1, m, pos);
}
Dfs(1, n);
printf("%lld\n", ans);
return 0;
}4.斯坦纳树（雾）
今天突然想起来这个东西，之前做过一个题，然而并没有记住，南昌邀请赛A题就GG了。今天整理一下（不过他好像不算数据结构）
可以用DP求解，dp[i][state]表示以i为根，指定集合中的点的连通状态为state的生成树的最小总权值。
转移方程有两重：
第一重，先通过连通状态的子集进行转移。dp[i][state]=min{ dp[i][subset1]+dp[i][subset2] } 枚举子集的技巧可以用 for(sub=(state-1)&state;sub;sub=(sub-1)&state)。
第二重，在当前枚举的连通状态下，对该连通状态进行松弛操作。dp[i][state]=min{ dp[i][state], dp[j][state]+e[i][j] }
为什么只需对该连通状态进行松弛？因为更后面的连通状态会由先前的连通状态通过第一重转移得到，所以无需对别的连通状态松弛。松弛操作用SPFA即可。
复杂度 O(n3^k+cE2^k)
/*
[WC2008]游览计划
就比较模板的题，但是输出路径的时候卡住了
之前的输出路径都是一条链走下来，这个不一定，可能回分叉
所以加一点特判
*/
#include<bits/stdc++.h>
#define maxn 60010
using namespace std;
int n, m, num, st[11][11], f[11][11][maxn], vis[11][11][maxn], g[11][11];
char as[11][11];
int pre[11][11][maxn][3];
struct node {
int x, y;
};
queue<node> q;
int xx[4] = {0, 0, 1, -1};
int yy[4] = {1, -1, 0, 0};
void SPFA(int s) {
while (!q.empty()) {
node now = q.front();
q.pop();
vis[now.x][now.y][s] = 0;
for (int k = 0; k < 4; k++) {
int nx = now.x + xx[k];
int ny = now.y + yy[k];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
int ss = s | st[nx][ny];
if (f[nx][ny][ss] > f[now.x][now.y][s] + g[nx][ny]) {
f[nx][ny][ss] = f[now.x][now.y][s] + g[nx][ny];
pre[nx][ny][ss][0] = now.x;
pre[nx][ny][ss][1] = now.y;
pre[nx][ny][ss][2] = s;
if (ss == s && vis[nx][ny][ss] == 0) {
vis[nx][ny][ss] = 1;
q.push(node{nx, ny});
}
}
}
}
}
}
void Dfs(int x, int y, int s) {
as[x][y] = 'o';
int nx = pre[x][y][s][0];
int ny = pre[x][y][s][1];
int ss = pre[x][y][s][2];
if (!ss) return;
Dfs(nx, ny, ss);
if (nx == x && ny == y)Dfs(x, y, (s - ss) | st[x][y]);
}
int main() {
scanf("%d%d", &n, &m);
int has = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &g[i][j]);
if (g[i][j] == 0) {
num++;
has = 1;
st[i][j] = 1 << num - 1;
}
}
memset(f, 127 / 3, sizeof(f));
int lim = 1 << num;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (st[i][j])f[i][j][st[i][j]] = 0;
for (int s = 1; s < lim; s++) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (st[i][j] && !(s & st[i][j]))continue;
for (int ss = (s - 1) & s; ss; ss = (ss - 1) & s) {
int x = ss | st[i][j];
int y = (s - ss) | st[i][j];
if (f[i][j][s] > f[i][j][x] + f[i][j][y] - g[i][j]) {
f[i][j][s] = f[i][j][x] + f[i][j][y] - g[i][j];
pre[i][j][s][0] = i;
pre[i][j][s][1] = j;
pre[i][j][s][2] = x;
}
}
if (f[i][j][s] < f[0][0][0] && vis[i][j][s] == 0) {
q.push(node{i, j});
vis[i][j][s] = 1;
}
}
SPFA(s);
}
int ans = 1e9;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans = min(ans, f[i][j][lim - 1]);
if (has == 0)ans = 0;
printf("%d\n", ans);
int ok = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (st[i][j]) {
Dfs(i, j, lim - 1);
ok = 1;
break;
}
if (ok)break;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
if (g[i][j] == 0)printf("x");
else if (as[i][j] == 'o')printf("o");
else printf("_");
printf("\n");
}
return 0;
}HDU4085 Peach Blossom Spring
/*
根据题目，并不是给定集合互相可达，而是匹配
其实就是斯坦纳森林，先把互相可达的状态跑出来
然后重新dp一下
*/
#include<bits/stdc++.h>
#define maxn 60010
using namespace std;
int T, n, m, k, f[51][maxn], dp[maxn], vis[51][maxn], st[51];
struct edge {
int v, t;
};
vector<edge> G[51];
queue<int> q;
void SPFA(int s) {
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u][s] = 0;
for (edge e:G[u]) {
int ss = s | st[e.v];
if (f[e.v][ss] > f[u][s] + e.t) {
f[e.v][ss] = f[u][s] + e.t;
if (ss == s & vis[e.v][ss] == 0) {
vis[e.v][ss] = 1;
q.push(e.v);
}
}
}
}
}
bool check(int x) {
int r = 0;
for (int i = 0; x; i++, x >>= 1)
r += (x & 1) * (i < k ? 1 : -1);
return r == 0;
}
bool ok(int x) {
if (x <= k)return 1;
if (n - x < k)return 1;
return 0;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
G[i].clear();
st[i] = 0;
}
int u, v, t;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &u, &v, &t);
G[u].push_back(edge{v, t});
G[v].push_back(edge{u, t});
}
int lim = 1 << (2 * k);
memset(f, 127 / 3, sizeof(f));
memset(vis, 0, sizeof(vis));
int p = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = 0;
if (ok(i)) {
p++;
st[i] = 1 << p - 1;
f[i][st[i]] = 0;
}
}
for (int s = 0; s < lim; s++) {
for (int i = 1; i <= n; i++) {
if (st[i] && !(s & st[i]))continue;
for (int j = s & (s - 1); j; j = (j - 1) & s) {
f[i][s] = min(f[i][s], f[i][j | st[i]] + f[i][(s - j) | st[i]]);
}
if (f[i][s] < f[0][0]) {
q.push(i);
vis[i][s] = 1;
}
}
SPFA(s);
}
for (int j = 0; j < lim; j++) {
dp[j] = f[0][0];
for (int i = 1; i <= n; i++)
dp[j] = min(dp[j], f[i][j]);
}
for (int i = 1; i < lim; i++)
if (check(i))
for (int j = i & (i - 1); j; j = (j - 1) & i)
if (check(j))dp[i] = min(dp[i], dp[j] + dp[i - j]);
if (dp[lim - 1] >= f[0][0])printf("No solution\n");
else printf("%d\n", dp[lim - 1]);
}
return 0;
}南昌邀请赛A题
#include<bits/stdc++.h>
#define maxn 60010
using namespace std;
int n, m, st[maxn], f[50][maxn], vis[50], dp[maxn];
map<string, int> mp;
queue<int> q;
struct edge {
int v, t;
};
vector<edge> G[maxn];
void SPFA(int s) {
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for (edge e:G[u]) {
if (f[e.v][s] > f[u][s] + e.t) {
f[e.v][s] = f[u][s] + e.t;
if (vis[e.v] == 0) {
vis[e.v] = 1;
q.push(e.v);
}
}
}
}
}
bool ok(int s) {
for (int i = 1; i <= 8; i += 2)
if (((s >> i - 1) & 1) ^ ((s >> i) & 1))return 0;
return 1;
}
int main() {
scanf("%d%d", &n, &m);
string name;
for (int i = 1; i <= n; i++) {
cin >> name;
mp[name] = i;
}
string su, sv;
int u, v, t;
for (int i = 1; i <= m; i++) {
cin >> su >> sv >> t;
u = mp[su], v = mp[sv];
G[u].push_back(edge{v, t});
G[v].push_back(edge{u, t});
}
memset(f, 127 / 3, sizeof(f));
for (int i = 1; i <= 8; i++) {
cin >> su;
u = mp[su];
f[u][1 << i - 1] = 0;
}
int lim = 1 << 8;
for (int s = 1; s < lim; s++) {
for (int i = 1; i <= n; i++) {
for (int j = s & (s - 1); j; j = (j - 1) & s) {
f[i][s] = min(f[i][s], f[i][j] + f[i][s - j]);
}
if (f[i][s] < f[0][0]) {
vis[i] = 1;
q.push(i);
}
}
SPFA(s);
}
for (int i = 0; i < lim; i++) {
dp[i] = 1e9;
if (ok(i)) {
for (int j = 1; j <= n; j++)
dp[i] = min(dp[i], f[j][i]);
}
}
for (int i = 0; i < lim; i++)
if (ok(i))
for (int j = i & (i - 1); j; j = (j - 1) & i)
dp[i] = min(dp[i], dp[j] + dp[i - j]);
printf("%d\n", dp[lim - 1]);
return 0;
}
/*
4 4
1
2
3
4
1 2 5
1 3 2
1 4 6
2 3 100
1 2
3 4
1 3
2 4
*/5 李超树
之前一直以为这个树是个什么新的数据结构，今天看了看才发现好像就是一个标记永久化的线段树
解决的经典问题就是平面n条线段，支持在线加边，然后询问x位置的ymax
如果只n条直线的话应该也可以平衡树做
线段树按x轴建，插入新的线段的时候到某个区间，若区间空，则覆盖；若新的严格好于旧的，则覆盖；若有交点，就稍微讨论一下，把不确定的半个区间下放到孩子。最后取根到叶子路径上的所有直线max
/*
[JSOI2008]Blue Mary开公司
放直线 单点查max
*/
#include<bits/stdc++.h>
#define maxn 500010
#define db long double
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
using namespace std;
int n, m;
struct node {
db k, b;
int has;
} s[maxn * 4];
int dcmp(db x) {
if (fabs(x) <= 1e-6)return 0;
if (x > 0)return 1;
else return -1;
}
db get(db k1, db b1, db k2, db b2) {
if (dcmp(k1 - k2) == 0)return -1;
return (b2 - b1) / (k1 - k2);
}
void Build(int k, int l, int r) {
s[k].has = 0;
if (l == r)return;
Build(lc, l, mid);
Build(rc, mid + 1, r);
}
void Insert(int k, int l, int r, db K, db B) {
if (s[k].has == 0) {
s[k].has = 1;
s[k].k = K;
s[k].b = B;
return;
}
if (l == r) {
if (s[k].k * l + s[k].b < K * l + B) {
s[k].k = K;
s[k].b = B;
}
return;
}
db c = get(s[k].k, s[k].b, K, B);
if(c==-1&&B>s[k].b){
s[k].k = K;
s[k].b = B;
return;
}
if (c <= mid) {
if (dcmp(s[k].k - K) >= 0) {
Insert(lc, l, mid, K, B);
} else {
Insert(lc, l, mid, s[k].k, s[k].b);
s[k].k = K;
s[k].b = B;
}
} else {
if (dcmp(s[k].k - K) >= 0) {
Insert(rc, mid + 1, r, s[k].k, s[k].b);
s[k].k = K;
s[k].b = B;
} else {
Insert(rc, mid + 1, r, K, B);
}
}
}
db Query(int k, int l, int r, int x) {
if (s[k].has == 0)return 0;
db res = s[k].k * x + s[k].b;
if (l == x && r == x) return res;
if (x <= mid)res = max(res, Query(lc, l, mid, x));
else res = max(res, Query(rc, mid + 1, r, x));
return res;
}
int main() {
ios::sync_with_stdio(0);
cin >> m;
n = 50000;
string s;
db k, b;
int x;
Build(1, 1, n);
for (int i = 1; i <= m; i++) {
cin >> s;
if (s == "Project") {
cin >> b >> k;
b -= k;
Insert(1, 1, n, k, b);
} else {
cin >> x;
if (x < 1 || x > n) {
cout << 0 << endl;
continue;
}
cout << int(Query(1, 1, n, x) / 100) << endl;
}
}
return 0;
}
/*
6
Project 5 0
Project 1 1
Query 4
Project 100 0
Query 10
Query 110
*/另一道稍微复杂些的题目
/*
[SDOI2016]游戏
树上两点之间信息修改&&两点之间查询min
利用树剖对应到线段上
/*
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
#define maxn 100010
#define lc k*2
#define rc k*2+1
#define mid (l+r)/2
using namespace std;
ll n, m, num, cnt, head[maxn], sum[maxn], son[maxn], dep[maxn];
ll c[maxn], fa[maxn], top[maxn], d[maxn], cc[maxn];
struct A {
ll k, b, v;
} s[maxn * 4];
const ll bas = 123456789123456789ll;
struct node {
ll v, pre, t;
} e[maxn * 2];
void Add(ll from, ll to, ll dis) {
num++;
e[num].v = to;
e[num].t = dis;
e[num].pre = head[from];
head[from] = num;
}
ll Dfs1(ll now, ll from, ll deep, ll dis) {
fa[now] = from;
dep[now] = deep;
sum[now] = 1;
d[now] = dis;
for (ll i = head[now]; i; i = e[i].pre) {
ll v = e[i].v;
if (v == from)continue;
sum[now] += Dfs1(v, now, deep + 1, dis + e[i].t);
if (sum[son[now]] < sum[v])
son[now] = v;
}
return sum[now];
}
void Dfs2(ll now, ll str, ll from) {
c[now] = ++cnt;
cc[cnt] = now;
top[now] = str;
if (!son[now])return;
Dfs2(son[now], str, now);
for (ll i = head[now]; i; i = e[i].pre) {
ll v = e[i].v;
if (v == from || v == son[now])continue;
Dfs2(v, v, now);
}
}
void Build(ll k, ll l, ll r) {
s[k].k = 0;
s[k].b = bas;
s[k].v = bas;
if (l == r)return;
Build(lc, l, mid);
Build(rc, mid + 1, r);
}
void in(ll k, ll l, ll r, ll K, ll B) {
ll lx = s[k].k * d[cc[l]] + s[k].b;
ll lxx = K * d[cc[l]] + B;
ll rx = s[k].k * d[cc[r]] + s[k].b;
ll rxx = K * d[cc[r]] + B;
if (lxx >= lx && rxx >= rx)return;
if (lxx <= lx && rxx <= rx) {
s[k].k = K;
s[k].b = B;
s[k].v = min(s[k].v, min(lxx, rxx));
return;
}
ll mx = s[k].k * d[cc[mid]] + s[k].b;
ll mxx = K * d[cc[mid]] + B;
if (lx < lxx) {
if (mx > mxx) {
in(lc, l, mid, s[k].k, s[k].b);
s[k].k = K;
s[k].b = B;
s[k].v = min(lxx, rxx);
} else {
in(rc, mid + 1, r, K, B);
}
} else {
if (mx > mxx) {
in(rc, mid + 1, r, s[k].k, s[k].b);
s[k].k = K;
s[k].b = B;
s[k].v = min(lxx, rxx);
} else {
in(lc, l, mid, K, B);
}
}
s[k].v = min(s[k].v, min(s[lc].v, s[rc].v));
}
void Insert(ll k, ll l, ll r, ll x, ll y, ll K, ll B) {
if (x <= l && y >= r) {
in(k, l, r, K, B);
return;
}
if (x <= mid)Insert(lc, l, mid, x, y, K, B);
if (y > mid)Insert(rc, mid + 1, r, x, y, K, B);
s[k].v = min(s[k].v, min(s[lc].v, s[rc].v));
}
ll Query(ll k, ll l, ll r, ll x, ll y) {
if (x <= l && y >= r)return s[k].v;
ll res = bas;
res = min(res, s[k].k * d[cc[max(l, x)]] + s[k].b);
res = min(res, s[k].k * d[cc[min(r, y)]] + s[k].b);
if (x <= mid)res = min(res, Query(lc, l, mid, x, y));
if (y > mid)res = min(res, Query(rc, mid + 1, r, x, y));
return res;
}
void Insertsum(ll x, ll y, ll K, ll B) {
ll fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] >= dep[fy]) {
Insert(1, 1, n, c[fx], c[x], K, B);
x = fa[fx];
} else {
Insert(1, 1, n, c[fy], c[y], K, B);
y = fa[fy];
}
fx = top[x];
fy = top[y];
}
if (c[x] <= c[y])Insert(1, 1, n, c[x], c[y], K, B);
else Insert(1, 1, n, c[y], c[x], K, B);
}
ll Querysum(ll x, ll y) {
ll res = bas, fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] >= dep[fy]) {
res = min(res, Query(1, 1, n, c[fx], c[x]));
x = fa[fx];
} else {
res = min(res, Query(1, 1, n, c[fy], c[y]));
y = fa[fy];
}
fx = top[x];
fy = top[y];
}
if (c[x] <= c[y])res = min(res, Query(1, 1, n, c[x], c[y]));
else res = min(res, Query(1, 1, n, c[y], c[x]));
return res;
}
ll LCA(ll x, ll y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]])swap(x, y);
x = fa[top[x]];
}
if (dep[x] < dep[y])swap(x, y);
return y;
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
ll x, y, z;
for (ll i = 1; i < n; i++) {
cin >> x >> y >> z;
Add(x, y, z);
Add(y, x, z);
}
Dfs1(1, -1, 0, 0);
Dfs2(1, 1, -1);
Build(1, 1, n);
ll s, t, a, b, op, K, B, lca;
while (m--) {
cin >> op;
if (op == 1) {
cin >> s >> t >> a >> b;
lca = LCA(s, t);
K = -a;
B = b + a * d[s];
Insertsum(s, lca, K, B);
K = a;
B = b + a * d[s] - 2 * a * d[lca];
Insertsum(lca, t, K, B);
} else {
cin >> s >> t;
cout << Querysum(s, t) << endl;
}
}
return 0;
}
京公网安备 11010502036488号