数据结构优化

数据结构优化¶

[NOI2020] 命运¶

题目描述

提示：我们在题目描述的最后一段提供了一份简要的、形式化描述的题面。

在遥远的未来，物理学家终于发现了时间和因果的自然规律。即使在一个人出生前，我们也可以通过理论分析知晓他或她人生的一些信息，换言之，物理学允许我们从一定程度上“预言”一个人的“命运”。

简单来说，一个人的命运是一棵由时间点构成的有根树 \(T\)：树的根结点代表着出生，而叶结点代表着死亡。每个非叶结点 \(u\) 都有一个或多个孩子 \(v_1, v_2,\dots , v_{c_u}\)，表示这个人在 \(u\) 所代表的时间点做出的 \(c_u\) 个不同的选择可以导向的不同的可能性。形式化的，一个选择就是树上的一条边 \((u, v_i)\)，其中 \(u\) 是 \(v_i\) 的父结点。

一个人的一生是从出生（即根结点）到死亡（即某一个叶子结点）的一条不经过重复结点的路径，这条路径上任何一个包含至少一条边的子路径都是这个人的一段**人生经历**，而他或她以所有可能的方式度过一生，从而拥有的所有人生经历，都被称为**潜在的人生经历**。换言之，所有潜在的人生经历就是所有 \(u\) 到 \(v\) 的路径，满足 \(u, v \in T\)，\(u \neq v\)，并且 \(u\) 是 \(v\) 的祖先。在数学上，这样一个潜在的人生经历被记作有序对 \((u, v)\)，树 \(T\) 所有潜在的人生经历的集合记作 \(\mathcal P_T\)。

物理理论不仅允许我们观测代表命运的树，还能让我们分析一些潜在的人生经历是否是“重要”的。一个人所作出的每一个选择——即树上的每一条边——都可能是**重要**或**不重要**的。一段潜在的人生经历被称为重要的，当且仅当其对应的路径上存在一条边是重要的。我们可以观测到一些潜在的人生经历是重要的：换言之，我们可以观测得到一个集合 \(\mathcal Q \subseteq \mathcal P_T\)，满足其中的所有潜在的人生经历 \((u, v) \in \mathcal Q\) 都是重要的。

树 \(T\) 的形态早已被计算确定，集合 \(\mathcal Q\) 也早已被观测得到，一个人命运的不确定性已经大大降低了。但不确定性仍然是巨大的——来计算一下吧，对于给定的树 \(T\) 和集合 \(\mathcal Q\)，存在多少种不同的方案确定每条边是否是重要的，使之满足所观测到的 \(\mathcal Q\) 所对应的限制：即对于任意 \((u, v) \in \mathcal Q\)，都存在一条 \(u\) 到 \(v\) 路径上的边被确定为重要的。

形式化的：给定一棵树 \(T = (V, E)\) 和点对集合 \(\mathcal Q \subseteq V \times V\) ，满足对于所有 \((u, v) \in \mathcal Q\)，都有 \(u \neq v\)，并且 \(u\) 是 \(v\) 在树 \(T\) 上的祖先。其中 \(V\) 和 \(E\) 分别代表树 \(T\) 的结点集和边集。求有多少个不同的函数 \(f\) : \(E \to \{0, 1\}\)（将每条边 \(e \in E\) 的 \(f(e)\) 值置为 \(0\) 或 \(1\)），满足对于任何 \((u, v) \in \mathcal Q\)，都存在 \(u\) 到 \(v\) 路径上的一条边 \(e\) 使得 \(f(e) = 1\)。由于答案可能非常大，你只需要输出结果对 \(998,244,353\)（一个素数）取模的结果。

输入格式

从文件 destiny.in 中读入数据。

第一行包含一个正整数 \(n\)，表示树 \(T\) 的大小，树上结点从 \(1\) 到 \(n\) 编号，\(1\) 号结点为根结点；

接下来 \(n - 1\) 行每行包含空格隔开的两个数 \(x_i, y_i\)，满足 \(1 \leq x_i, y_i \leq n\)，表示树上的结点 \(x_i\) 和 \(y_i\) 之间存在一条边，但并不保证这条边的方向；

接下来一行包含一个非负整数 \(m\)，表示所观测得到信息的条数。

接下来 \(m\) 行每行包含空格隔开的两个数 \(u_i, v_i\)，表示 \((u_i, v_i) \in \mathcal Q\)。请注意：输入数据可能包含重复的信息，换言之可能存在 \(i \neq j\)，满足 \(u_i = u_j\) 且 \(v_i = v_j\)。

输入数据规模和限制参见本题末尾的表格。

输出格式

输出到文件 destiny.out 中。

输出仅一行一个整数，表示方案数对 \(998, 244, 353\) 取模的结果。

样例 1 解释¶

共有 \(16\) 种方案，其中不满足题意的方案有以下 \(6\) 种：

\((1, 2),(2, 3),(3, 5)\) 确定为不重要，\((3, 4)\) 确定为重要：集合 \(\mathcal Q\) 中没有限制被满足。
\((1, 2),(2, 3),(3, 4),(3, 5)\) 确定为不重要：集合 \(\mathcal Q\) 中没有限制被满足。
\((1, 2),(2, 3)\) 确定为不重要，\((3, 4),(3, 5)\) 确定为重要：集合 \(\mathcal Q\) 中 \((1, 3)\) 没被满足。
\((1, 2),(2, 3),(3, 4)\) 确定为不重要，\((3, 5)\) 确定为重要：集合 \(\mathcal Q\) 中 \((1, 3)\) 没被满足。
\((2, 3),(3, 5)\) 确定为不重要，\((1, 2),(3, 4)\) 确定为重要：集合 \(\mathcal Q\) 中 \((2, 5)\) 没被满足。
\((2, 3),(3, 4),(3, 5)\) 确定为不重要，\((1, 2)\) 确定为重要：集合 \(\mathcal Q\) 中 \((2, 5)\) 没被满足。
其他方案下，集合 \(\mathcal Q\) 中的限制都被满足了。

样例 3¶

见选手目录下的 destiny/destiny3.in 与 destiny/destiny3.ans。

样例 4¶

见选手目录下的 destiny/destiny4.in 与 destiny/destiny4.ans。

测试点编号	\(n\)	\(m\)	\(T\) 为完全二叉树
\(1\sim 4\)	\(\le 10\)	\(\le 10\)	否
\(5\)	\(\le 500\)	\(\le 15\)	否
\(6\)	\(\le 10^4\)	\(\le 10\)	否
\(7\)	\(\le 10^5\)	\(\le 16\)	否
\(8\)	\(\le 5\times 10^5\)	\(\le 16\)	否
\(9\)	\(\le 10^5\)	\(\le 22\)	否
\(10\)	\(\le 5\times 10^5\)	\(\le 22\)	否
\(11\)	\(\le 600\)	\(\le 600\)	否
\(12\)	\(\le 10^3\)	\(\le 10^3\)	否
\(13\sim 14\)	\(\le 2\times 10^3\)	\(\le 5\times 10^5\)	否
\(15\sim 16\)	\(\le 5\times 10^5\)	\(\le 2\times 10^3\)	否
\(17\sim 18\)	\(\le 10^5\)	\(\le 10^5\)	是
\(19\)	\(\le 5\times 10^4\)	\(\le 10^5\)	否
\(20\)	\(\le 8\times 10^4\)	\(\le 10^5\)	否
\(21\sim 22\)	\(\le 10^5\)	\(\le 5\times 10^5\)	否
\(23\sim 25\)	\(\le 5\times 10^5\)	\(\le 5\times 10^5\)	否

测试点约束¶

全部数据满足：\(n \leq 5 \times 10^5\)，\(m \leq 5 \times 10^5\)。输入构成一棵树，并且对于 \(1 \leq i \leq m\)，\(u_i\) 始终为 \(v_i\) 的祖先结点。

完全二叉树：在本题中，每个非叶结点都有左右子结点，且所有叶子结点深度相同的树称为满二叉树；将满二叉树中的结点按照从上到下、从左向右的顺序编号，编号最小的若干个结点形成的树称为完全二叉树。

[NOI1998] 免费的馅饼¶

题目描述

SERKOI 最新推出了一种叫做“免费馅饼”的游戏：游戏在一个舞台上进行。舞台的宽度为 \(w\) 格（从左到右依次用 \(1\) 到 \(w\) 编号），游戏者占一格。开始时游戏者可以站在舞台的任意位置，手里拿着一个托盘。下图为天幕的高度为 \(4\) 格时某一个时刻游戏者接馅饼的情景。

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。

当馅饼在某一时刻恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。当馅饼落在一个游戏者不在的格子里时该馅饼就消失。

写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。

输入格式

第一行是用空格隔开的两个正整数，分别给出了舞台的宽度 \(w\) 和馅饼的个数 \(n\)。

接下来 \(n\) 行，每一行给出了一块馅饼的信息。

由三个正整数组成，分别表示了每个馅饼落到舞台上的时刻 \(t_i\)，掉到舞台上的格子的编号 \(p_i\)，以及分值 \(v_i\)。

游戏开始时刻为 \(0\)。

输入文件中同一行相邻两项之间用一个空格隔开。

输入数据中可能存在两个馅饼的 \(t_i\) 和 \(p_i\) 都一样。

输出格式

一个数，表示游戏者获得的最大总得分。

对于 \(100\%\) 的数据，\(1 \leq w \leq 10^8\)，\(1 \leq n \leq 10^5\)，\(1\leq t_i \leq 10^8\)，\(1\leq p_i \leq w\)，\(1\leq v_i \leq 1000\)。

思路¶

好经典的玩法

咳咳，我们来看题目。简化题意，你有一个指针，每一秒可以向左向右移动一个单位。给定n个条件，当在t_i时刻指针处于p_i，就可以得1分。求最高得分。

那么我们设定f_i为表示拿到了第i个得分条件时最大得分。

那么考虑转移。很显然，我们可以从特点的某些f_j处转移。形式化地，有\(f_i=\max(f_i,v_i+f_j),|p_i-p_j|≤2t_i-2t_j\)

那么我们就需要一个可以维护最小值的数据结构来维护符合条件的最小值。我们可以想到的是线段树，但是显然我们需要对条件进行一些变形。很显然我们需要把上面的不等式按下标移项，那么我们就需要讨论那烦人的绝对值了。

若\(p_i>p_j\)，则变形为\(p_i-p_j≤2t_i-2t_j\)，即\(2t_j-p_j≤2t_i-p_i\)
若\(p_i<p_j\)，则变形为\(-p_i+p_j≤2t_i-2t_j\)，即\(p_j+2t_j≤2t_i+p_i\)

那这咋办呢？二维线段树是不可敲的。

我们需要查询p_j满足\(p_i-t_i+t_j≤p_j≤p_i+t_i-t_j\)。我们发现，当\(t_i-t_j>0\)大前提成立时，若\(p_i-p_j≤2t_i-2t_j\)成立，则必有\(p_i>p_j\)。另外一个同理。因此，我们只需要满足下面即可

\(2t_j-p_j≤2t_i-p_i\)且\(p_j+2t_j≤2t_i+p_i\)。因此是一个二维偏序问题。

思考一下：为什么是“且”？

#include<bits/stdc++.h>
#define rep(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define per(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
#define int long long
#define pii pair<int,int>

#define lc(x) (x<<1)
#define rc(x) (x<<1|1)

#define rd read()
int read(){
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
    return xx*ff;
}
void write(int out){
    if(out<0) putchar('-'),out=-out;
    if(out>9) write(out/10);
    putchar(out%10+'0');
}

const int N=2e5+15;
const int INF=1e9+5;
const int MOD=998244353;


int b[N],w,n,k,c[N];

struct node{
    int t,p,v,l,r;
}a[N];
bool cmpl(node x,node y){
    return x.l>y.l;
}
bool cmpr(node x,node y){
    return x.r<y.r;
}

void update(int x,int val){
    while(x<=k){
        c[x]=max(c[x],val);
        x+=x&-x;
    }
}

int query(int x){
    int res=0;
    while(x){
        res=max(res,c[x]);
        x-=x&-x;
    }
    return res;
}

signed main(){
    w=rd,n=rd;
    for(int i=1;i<=n;i++){
        a[i].t=rd,a[i].p=rd,a[i].v=rd;
        a[i].l=a[i].p-2*a[i].t;
        a[i].r=b[i]=a[i].p+2*a[i].t;
    }

    sort(a+1,a+n+1,cmpr);
    sort(b+1,b+n+1);
    k=unique(b+1,b+n+1)-b;
    for(int i=1;i<=n;i++)
        a[i].r=lower_bound(b+1,b+n+1,a[i].r)-b;

    sort(a+1,a+n+1,cmpl);
    for(int i=1;i<=n;i++){
        int tmp=query(a[i].r);
        update(a[i].r,tmp+a[i].v);//对于刚转移得到的dp值tmp，加入到树状数组里
    }
    cout<<query(k);
    return 0;
}