预防我咕，所以先粘一下官方题解
Solution: 构造字符串
容易将问题转化为若干个位置对应相等，若干位置不同
先将相同的合并在一起，然后不同的连边来处理不同的限制
如果同块连边，即无解
要求字典序最小，可以依次对于每个位置进行贪心
如果当前位置相同的块中已经确定了，直接取
否则找到所有要求不同的位置值的mex
直接实现上述做法，复杂度为\(O(nm\alpha(n))\)，这题放过暴力（所以数据也是乱造的
实际上可以通过倍增+并查集来实现合并，不同的关系只有\(m\)条，可以直接暴力处理贪心
ps:如果字符集大小有上限，我出题人就不会写了。。
注意sb细节，比如 \(x+z,y+z > n\) 的情况。
Solution: 寻宝
四联通和传送门都看做是边，可以做一个有向图强连通缩点
在得到的DAG上，用bitset维护连通关系即可
ps:如果你内存有点紧，分析可以知道强连通缩点后连通块数量上限为\(\frac{nm}{2}\)
实际上数据也完全不满，完全不用担心bitset内存不够
？？？ 题解说了个shit
直接bfs给图染个色，同一个连通块内都能到达，再给传送门起点和终点所在的连通块连个边，dfs就可以求出每个连通块能到那些连通块。
然后查询直接判断即可。
不过我在虚拟机上最慢跑了0.8s，TLEcoders上最慢的竟然只有50ms
Solution: 序列
容易发现这是一个与斜率有关的题目，这种题目通常通过维护凸包，或者李超树维护
跨过\(p_i\)的区间容易转化为：以\(p_i\)为右端点的最优+以\(p_{i}+1\)为左端点的最优
两个问题同理，以右端点为例
设\(sa_i=\sum_{j=1}^i a_j\)，\(sb_i=\sum_{j=1}^ib_j\)
最优即\(\max_{1\leq l\leq r}\{(sa_{r}-sa_{l-1})-k(sb_{r}-sb_{l-1})\}\)
即\(sa_r-k\cdot sb_{r}-\min_{0\leq l<r}\{ksb_{l}-sa_l\}\)，离线之后李超树维护直线即可
时间复杂度为\(O(n\log n)\)，常数略大，空间复杂度为\(O(n)\)
是个李超树的版，然而之前的李超树是拍的，考场上想了斜率，但并不知道如何维护，于是死了。
推个简单的式子：
\[\begin{aligned} &\sum_{i=l}^{r}a_{i}-k\sum_{i=l}^{r}b_{i} \\ &=pre_{r,a}-pre_{l-1,a}-k(pre_{r,b}-pre_{l-1,b}) \\ &=pre_{r,a}-pre_{l-1,a}-k\cdot pre_{r,b}+k\cdot pre_{l-1,b} \\ &=-k\cdot pre_{r,b}+pre_{r,a}+k\cdot pre_{l-1,b}-pre_{l-1,a} \end{aligned} \]要让总和最大，只需要让前两项和后两项分别最大，一加就是最大的值的了。
将 \(pre_{b}\) 看做直线的 \(k\) ，\(pre_{a}\) 看做直线的 \(b\) 。
将询问离线后按 \(p\) 排序，那个指针瞎jb走，依次加入满足条件的直线，然后查询即可。
前两项和后两项分开做就行，注意一些细节。
Code
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using std::max;
using std::sort;
#define re register
const int K = 1e6;
const int MAX = 1e6+3;
#define int long long
const int INF = -1e13+7;
#define scanf oma=scanf
#define freopen file=freopen
int oma;
FILE* file;
namespace some
{
struct stream
{
template<typename type>inline stream &operator >>(type &s)
{
bool w=0; s=0; char ch=getchar();
while(!isdigit(ch)){ w|=ch=='-'; ch=getchar(); }
while(isdigit(ch)){ s=(s<<1)+(s<<3)+(ch^48); ch=getchar(); }
return s=w?-s:s,*this;
}
}cin;
int n,m;
int ans[MAX];
struct node
{ int a,b; }q1[MAX],pre[MAX];
struct data
{
int p,k,i;
inline friend bool operator <(const data &a,const data &b)
{ return a.p<b.p; }
}q2[MAX];
#define debug(s) printf("%s\n",s)
}using namespace some;
namespace Data_Structures
{
struct segment
{
int k,b;
int y(int x)
{ return k*x+b; }
}seg[MAX];
struct Segment_Tree
{
int st[MAX<<3];
#define ls(p) p<<1
#define rs(p) p<<1|1
#define mid (l+r>>1)
void insert(int p,int l,int r,int x)
{
if(l==r)
{
if(seg[x].y(l)>seg[st[p]].y(l))
{ st[p] = x; }
return ;
}
if(!st[p])
{ st[p] = x; return ; }
if(seg[x].k<seg[st[p]].k)
{
if(seg[x].y(mid)<seg[st[p]].y(mid))
{ insert(ls(p),l,mid,x); }
else
{ insert(rs(p),mid+1,r,st[p]); st[p] = x; }
}
else if(seg[x].k>seg[st[p]].k)
{
if(seg[x].y(mid)<seg[st[p]].y(mid))
{ insert(rs(p),mid+1,r,x); }
else
{ insert(ls(p),l,mid,st[p]); st[p] = x; }
}
else if(seg[x].b>seg[st[p]].b)
{ st[p] = x; }
}
int query(int p,int l,int r,int x)
{
if(l==r)
{ return seg[st[p]].y(x); }
int res = seg[st[p]].y(x);
if(st[ls(p)]&&x<=mid)
{ res = max(res,query(ls(p),l,mid,x)); }
else if(st[rs(p)])
{ res = max(res,query(rs(p),mid+1,r,x)); }
return res;
}
}Tree;
}using namespace Data_Structures;
namespace OMA
{
auto main = []() -> signed
{
//#define local
#ifdef local
debug("look here! if you want submit,please closed this");
freopen("node.in","r",stdin); freopen("my.out","w",stdout);
#endif
freopen("seq.in","r",stdin); freopen("seq.out","w",stdout);
cin >> n >> m;
for(re int i=1; i<=n; i++)
{ pre[i].a = pre[i-1].a+(cin >> q1[i].a,q1[i].a),pre[i].b = pre[i-1].b+(cin >> q1[i].b,q1[i].b); }
for(re int i=1; i<=m; i++)
{ cin >> q2[i].p >> q2[i].k; q2[i].i = i; }
//for(re int i=1; i<=n; i++)
//{ printf("%lld %lld\n",pre[i].a,pre[i].b); }
sort(q2+1,q2+1+m); int p = 1;
seg[n+1] = (segment){0,0}; Tree.insert(1,-K,K,n+1);
for(re int i=1; i<=m; i++)
{
//printf("%lld\n",q2[i].i);
while(p<q2[i].p)
{ seg[p] = (segment){pre[p].b,-pre[p].a}; Tree.insert(1,-K,K,p); p++; }
ans[q2[i].i] = Tree.query(1,-K,K,q2[i].k);
} // l-1
//for(re int i=1; i<=m; i++)
//{ printf("ans[%lld]=%lld\n",i,ans[i]); }
p = n; memset(Tree.st,0,sizeof(Tree.st));
for(re int i=m; i; i--)
{
while(p>=q2[i].p)
{ seg[p] = (segment){-pre[p].b,pre[p].a}; Tree.insert(1,-K,K,p); p--; }
ans[q2[i].i] += Tree.query(1,-K,K,q2[i].k); //printf("query(%lld)=%lld\n",q2[i].p,Tree.query(1,-K,K,q2[i].k));
} // r
for(re int i=1; i<=m; i++)
{ printf("%lld\n",ans[i]); }
return 0;
};
};
signed main()
{ return OMA::main(); }
Solution: 构树
不会，所以我咕了
（实际上应该是数树）
给了非多项式算法非常多分吧
Algorithm1：枚举
直接枚举所有的树，一共\(n^{n-2}\)种，根据不同枚举方法会带有不同的\(n^w\)
比如直接枚举prufer序列
Algorithm2：状压dp
假装我们的树是一颗以1为根的有根树，模拟展开dfs子树关系的过程
另\(dp_{i,S,j}\)表示以\(i\)为根，子树里已经已经有\(S\)集合的节点，有\(j\)条边相同
然后为一个\(dp_{i,S,j}\)枚举一个儿子\(v\)以及其子树\(T\)进行合并，注意合并顺序防止重复
（比如可以保证\(S-\{i\}\)中最大编号的点<\(T\)中最大编号的点）
复杂度为\(O(3^n n^w)\)，\(n\leq 15\)是给这个算法的
Algorithm3：Poly算法
要做多项式复杂度的算法，首先需要一点计数的辅助
Cayley公式：一个完全图有\(n^{n-2}\)棵无根生成树，经典问题prufer序列证明
扩展Cayley公式：被确定边分为大小为\(a_1,a_2,\cdots, a_m\)的连通块，则有\(n^{m-2}\prod {a_i}\)种生成树
证明就不再赘述了
那么我们可以通过 强制一条边出现或者是不出现 来统计边数
通过扩展Cayley公式统计强制的边能够得到多少树
比较Naive的想法，我们可以直接在dp中记录连通块大小、相同边数
每次断开一个连通块，乘上一个\(n\)的系数
强制相同的边，直接合并两个连通块即可
\(dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i+k,j+l+1}\)
强制不同的边，用不合并的-合并的即可得到
\(nk\cdot dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i,j+l}\)
\(-dp_{u,i,j}\cdot dp_{v,k,l}\rightarrow dp_{u,i+k,j+l}\)
预计分数：不知道
优化
首先优化连通块大小，可以通过一个经典的转化：
\(size\)作为系数，转化为在这个连通块中选出一个关键点（很显然\(size\)多大，就有多少中选出一个关键点的方案）
这样这一位被压缩到\(0,1\)，只需要记录是否在这个连通块中选择了关键点
这样复杂度等同于经典树形背包问题，但是空间略紧张
可以将第3维用拉格朗日插值换掉
设答案数列为\(a_i\)，转化为多项式\(A(x)=\sum_{i=0} a_ix^i\)
带入\(x_0=0,1,\cdots ,n\)，求得\(A(x_0)\)的数值，然后插值得到多项式
这样第三维就合并可以直接用\(x_0^k\)换掉