初赛考完了，对了一下答案应该是89分
不知道分数线多少。
初赛复习：前缀表达式和后缀表达式
前缀表达式和后缀表达式——有时也被成为波兰表达式和逆波兰表达式——是对仅包含二元关系运算符和括号的表达式的变形。
事实上，前缀表达式和后缀表达式没有本质区别，因此只要会了前缀表达式，就会了后缀表达式——记住，前缀表达式是把运算符提到最前面的表达式，而后缀表达式反之。
对于一个这样的式子：
a+b/c
我们按照运算符优先级依次操作：
a+/bc
+a/bc
这样就将所有符号提到了整个式子的最前面。
对于包含括号的表达式，例如：
2+3(4-(5+6))/7
操作流程依然是按照运算符优先级的。
2+3(4-+5 6)/7
2+3(-4+5 6)/7
2+3(-4+5 6)/7
2+/3-4+5 6 7
+2/3-4+5 6 7
而如果要求后缀表达式，那操作就反之——从优先级最低的操作符开始，把操作符提到最右边。
还是一样的例子：
2 3(4-(5+6))/7+
2 3(4-(5+6))7/+
2 3(4-(5+6))7/+
2 3(4(5+6)-)7/+
2 3 4 5 6+-*7/+
初赛复习：OSI七层网络协议
ISO网络协议标准包括七层。
最底层的被称为物理层。这一层主要包括：
光纤、同轴电缆、双绞线、网卡、中继器、集线器
等硬件。它传输的是比特（bit）
物理层之上被称为数据链路层。数据链路层的主要硬件是网桥和交换机，这一层把数据封装成一种被称为帧（frame）的结构。
网络层是第三层。IP地址是这一层的内容。路由器也在这一层。
传输层是网络层之上的第四层。这一层主要管的是数据包的运输。TCP协议和UDP协议都是传输层协议。
会话层是第五层，没看到什么考点。
表示层主要负责数据转换，没看到什么考点。
应用层是最顶层，应用层协议包括Telnet（Windows的远程桌面）、FTP、SNMP（这两个都是远程文件管理系统）、HTTP、DNS（IP地址解析服务）等协议。它是直接展现给用户的一层。
初赛复习：主定理
对于形如：
$$T(n)=aT(\frac{n}{b})+f(n)$$
那么，我们可以用下述三个公式来刻画\(T(n)\)的渐近上下界。
$$f(n)=\Theta(n^{log_ba-\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(n^{log_ba})$$
$$f(n)=\Theta(n^{log_ba+\epsilon}),\epsilon >0\Rightarrow T(n)=\Theta(f(n))$$
$$f(n)=\Theta(n^{log_ba})\Rightarrow T(n)=\Theta(n^{log_ba}logn)$$
换而言之，就是，比较\(f(n)\)和\(\Theta(n^{log_ba})\)的级别。如果两者同级，就乘上一个log，否则就取较大的。
lp1341 无序字母对
仔细观察这题：考虑到字母对可以反向，我们不妨把它们看作无序数对。这就把题意转化为了，给你n个无序数对，让你找到一个n+1个数的序列，使得无序数对在序列的相邻两项中各自至少出现一次。
观察到这无序数对组和图的相似性，我们可以尝试把无序数对看成一条边，然后建一张图。在这种情况下，这个序列就是这张图上的一个遍历顺序，使得经过每一条边至少一次。
深入考虑，这个序列也只能经过每条边至多一次。这是因为，一条n条边的路径，恰好包含了n+1个点。
问题就转化为了欧拉路径问题。
判断一张图是否是半欧拉图是很容易的。一张半欧拉图中，恰好有两个点的度数为奇数——这两个点各自作为欧拉路径的起点和终点。
求解欧拉回路的方法是很容易的。对于每一个点，我们只需要找到与它相邻的所有环即可。
问题在于——这很不显然——为什么相同的求法放到欧拉路径上，只需从奇数入度点开始，就是合法的？
我们不妨把整个欧拉路径抽象成一条链上面挂着一堆环套环套环套环套环。一个令人好奇的问题是，为什么搜索的时候不会直接走到链的另一端，而是先把环跑完，或者反过来？
我们注意到把点加入答案数组的方式：对于两个栈——答案栈和搜索栈来说，点被加入的顺序是不仅相同的。
模拟一下，一个点能从搜索栈出来，被加入答案栈，当且仅当从这个点出发无路可走了。
显然，有且仅有终点是无路可走的。那么，无论终点是在什么时候被访问到的，只要它被访问到，那么它就会被立刻退出搜索栈并被加入答案栈，剩下的点也是同理。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int hash[200];int hsah[200];
int mp[60][60],in[60];
int n;
int st[3005],tp=0;
inline void dfs(int X){
for(int i=0;i<52;++i){
if(mp[X][i]){
printf("%d %d\n",X,i);
--mp[X][i],--mp[i][X];
dfs(i);
}
}
printf("%d\n",X);
st[++tp]=X;
}
void init(){
for(int i=0;i<26;++i){
hash['A'+i]=i;hash['a'+i]=i+26;
hsah[i]='A'+i;hsah[i+26]='a'+i;
}
scanf("%d",&n);
char ch[4];
for(int i=1;i<=n;++i){
std::cin>>ch+1;
++mp[hash[ch[1]]][hash[ch[2]]],++mp[hash[ch[2]]][hash[ch[1]]];
++in[hash[ch[1]]],++in[hash[ch[2]]];
}
int ans=0,nans=-1;
for(int i=0;i<52;++i){
if(in[i]&1){
++ans;
if(nans<0){nans=i;}
}
}
if(ans&&ans!=2){
puts("No Solution");
return;
}
if(!ans){
for(int i=0;i<52;++i){
if(in[i]){
nans=i;
break;
}
}
}
dfs(nans);
if(tp!=n+1){
puts("No Solution");
return;
}
while(tp){
putchar(hsah[st[tp--]]);
}
}
int main(){
init();
return 0;
}
lp4027 NOI2007 货币兑换
我们观察到，整个行为一定能被拆分为全买和全卖。
略微思考一下就可以证明这个定理。倘若先部分买再部分买，再全卖，显然不是优的。因为我们总可以找到更优的部分，使得全买再全卖更优；同理，部分卖再部分卖也一定不会更优。这是因为，券是必须按比例卖出的。 于是，我们就把整个决策拆分为很多个全买和全卖交替出现的点，然后对这些点进行DP。
我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A，那么购买的数量是x/A，那么购买了B的数量是x/(A*Rate)，花费的钱是xB/(A*Rate)。可以解得：
$$x=\frac{A*Rate*f_i}{RateA+B}$$
也就是说，购买的A和B券的数量分别是：
$$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$
那么，我们从j转移到i的方程是：
$$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$
我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是，斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中，这使得我们设\(f_j=y\)的计划破产了。 我们不妨设：
$$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$
那么我们可以得到： $$f_i=A_ix_j+B_iy_j$$
那么，当前点之前的所有点构成的就是平面上的一些点，然后我们要用这条直线去切这些点，找到截距最大的那个。
通过这个斜率优化，我们把问题如下转换：我们有一个仅包含第一象限的平面，有\(10^5\)个操作，每个操作可能是加入一个点，或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。
因此，我们对时间分治，然后左半部分对x坐标排序——这是为了维护凸包；对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线，都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的，因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn)
注意：要判一下分母不能等于极小数，否则可能会挂。
略微思考一下就可以证明这个定理。倘若先部分买再部分买，再全卖，显然不是优的。因为我们总可以找到更优的部分，使得全买再全卖更优；同理，部分卖再部分卖也一定不会更优。这是因为，券是必须按比例卖出的。 于是，我们就把整个决策拆分为很多个全买和全卖交替出现的点，然后对这些点进行DP。 我们不妨记\(f_{i}\)表示第i个点为止最多的钱数。倘若第i天花了x来购买A，那么购买的数量是x/A，那么购买了B的数量是x/(A*Rate)，花费的钱是xB/(A*Rate)。可以解得： $$x=\frac{A*Rate*f_i}{RateA+B}$$ 也就是说，购买的A和B券的数量分别是： $$\frac{Rate*f_i}{RateA+B},\frac{f_i}{RateA+B}$$ 那么，我们从j转移到i的方程是： $$f_j=Max(\frac{A_i*Rate_j*f_j}{Rate_jA_j+B_j}+\frac{B_i*f_j}{Rate_jA_j+B_j})$$ 我们考虑这个转移式要如何优化。 我们尝试对这个式子使用斜率优化。然而一个致命的问题是，斜率优化要求我们需要将方程中i的部分和j的部分独立地放在x,y,k,b中，这使得我们设\(f_j=y\)的计划破产了。 我们不妨设： $$x=\frac{Rate_i*f_i}{Rate_iA_i+B_i},y=\frac{f_i}{Rate_iA_i+B_i}$$ 那么我们可以得到： $$f_i=A_ix_j+B_iy_j$$ 那么，当前点之前的所有点构成的就是平面上的一些点，然后我们要用这条直线去切这些点，找到截距最大的那个。 通过这个斜率优化，我们把问题如下转换：我们有一个仅包含第一象限的平面，有\(10^5\)个操作，每个操作可能是加入一个点，或查询「经过任意一点的给定斜率的直线的最大截距」。 看起来这似乎需要可持久化凸包或者之类的复杂操作。但仔细观察我们发现这是一个可离线的操作。 因此，我们对时间分治，然后左半部分对x坐标排序——这是为了维护凸包；对右半部分按照斜率从大往小排序。那么对于新加进来的每一个直线，都只有可能找到凸包的下一个点。用单调栈即可。 围凸壳的复杂度是O(n)的，因此可以暴力重构。然后可以一边分治一边排序。 复杂度O(nlogn) 注意：要判一下分母不能等于极小数，否则可能会挂。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=100005;
const double eps=1E-10;
const double INF=1E10;
struct data{
double a;double b;double r;int id;double x;double y;
}a[N],b[N];
//斜率从大往小排序。
inline double cmp(const data &A,const data &B){
return A.a*B.b>B.a*A.b;
}
int n,st[N],tp=0;double m,f[N];
inline double icpt(int P,double A,double B){
// printf("icpt:%lf\n",a[P].x*A+a[P].y*B);
return a[P].x*A+a[P].y*B;
}
inline double slp(int A,int B){
if(fabs(a[A].x-a[B].x)<eps){
return INF;
}
return (a[A].y-a[B].y)/(a[A].x-a[B].x);
}
inline void mg(int l,int r){
int mid=(l+r)>>1;
int I=l,J=mid+1,tp=l;
while(I<=mid&&J<=r){
if(a[I].x<a[J].x){
b[tp++]=a[I++];
}else{
b[tp++]=a[J++];
}
}
while(I<=mid){
b[tp++]=a[I++];
}
while(J<=r){
b[tp++]=a[J++];
}
for(int i=l;i<=r;++i){
a[i]=b[i];
}
}
inline void cdq(int l,int r){
if(l==r){
f[l]=max(f[l],f[l-1]);
a[l].y=(double)f[l]/(a[l].r*a[l].a+a[l].b);
a[l].x=(double)a[l].r*a[l].y;
return;
}
int mid=(l+r)>>1;
int I=l,J=mid+1;
for(int i=l;i<=r;++i){
if(a[i].id<=mid){
b[I++]=a[i];
}else{
b[J++]=a[i];
}
}
for(int i=l;i<=r;++i){
a[i]=b[i];
}
cdq(l,mid);
tp=0;
for(int i=l;i<=mid;++i){
while(tp>1&&slp(st[tp],i)+eps>slp(st[tp-1],st[tp])){
--tp;
}
st[++tp]=i;
}
// printf("[%d,%d]\n",l,r);
// for(int i=1;i<=tp;++i){
// printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
// }
for(int i=mid+1;i<=r;++i){
while(tp>1&&slp(st[tp],st[tp-1])<=-a[i].a/a[i].b+eps){
--tp;
}
f[a[i].id]=max(f[a[i].id],icpt(st[tp],a[i].a,a[i].b));
// printf("%d %lf\n",i,a[i].ans);
}
cdq(mid+1,r);
mg(l,r);
}
void init(){
scanf("%d%lf",&n,&f[0]);
for(int i=1;i<=n;++i){
scanf("%lf%lf%lf",&a[i].a,&a[i].b,&a[i].r);
a[i].id=i;
}
std::sort(a+1,a+1+n,cmp);
cdq(1,n);
// for(int i=1;i<=n;++i){
// printf("%d:%lf,%lf %lf %lf\n",a[i].id,a[i].x,a[i].y,-(double)a[i].a/a[i].b,f[a[i].id]);
// }
printf("%.3lf\n",f[n]);
}
int main(){
init();
return 0;
}
lp2564 SCOI2009 生日礼物
尺取法即可。
开一个桶维护珍珠的颜色，然后扫一遍。每一次将最前端的点弹出，然后移动至下一个合法点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1000005;
struct data{
int id;
int val;
}a[N];
inline bool cmp(const data &A,const data &B){
return A.val<B.val;
}
int n,K,tp=0;
int bckt[65],cnt=0;
void init(){
scanf("%d%d",&n,&K);
int T;
for(int i=1;i<=K;++i){
scanf("%d",&T);
for(int j=1;j<=T;++j){
++tp;
scanf("%d",&a[tp].val);
a[tp].id=i;
}
}
std::sort(a+1,a+1+n,cmp);
int ans=2147483647;
int l=1,r=0;
while(r<n){
while(r<n){
++r;
if(!bckt[a[r].id]){
++cnt;
}
++bckt[a[r].id];
if(cnt==K){
break;
}
}
if(cnt==K){
ans=min(ans,a[r].val-a[l].val);
}
while(l<=r){
--bckt[a[l].id];
if(!bckt[a[l].id]){
--cnt;
++l;
break;
}
++l;
if(cnt==K){
// printf("%d %d %d\n",ans,l,r);
ans=min(ans,a[r].val-a[l].val);
}
}
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}
lp2219 HAOI2007 修筑绿化带
我们知道，如果我们确定了每个大矩形包含的权值最小的小矩形，那么我们只需要枚举一遍每一个大矩形并比较它们的回形部分的最大值。
那么我们考虑用单调队列来预处理出每一个小矩形的权值，然后用二维线段树来维护这个权值，那么我们可以在\(n^2log^2n\)的时间复杂度内完成这道题。
但仔细观察我们感觉\(n^2log^2n\)的时间复杂度对于\(1000\)的数据范围存在一定的困难。我们考虑是否存在一种\(n^2\)复杂度的做法。
有这样一道题叫做理想的正方形。这一题要求的是平面上矩形内最大值和最小值之差。显然，我们可以维护2n个单调队列来计算这个最大值。
那么，对于这题的强化板，我们该怎么做呢？
如果确定了右下角，那么整个矩形的权值是已经固定了的。那么，我们要求的就是那个矩形里面权值最小的子矩形。这一方面是和理想的正方形相同的。
我们不妨设\(c_{i,j}\)表示以(i,j)为右下角的绿化带能包括的花坛的最小值。问题就转变为怎么求出\(c_{i,j}\)。
仔细考虑这个问题，我们发现，每个花坛的最小值是可以预处理的。这样，我们就把这一题转化为了理想的正方形。
同样用二维单调队列维护即可。
需要注意边界条件较为复杂，且不要混淆单调队列里的数的意义。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=1005;
int n,m,A,B,C,D;
int val[N][N],sm[N][N],a[N][N],b[N][N];
deque<int> q[N],qq;
void init(){
scanf("%d%d%d%d%d%d",&n,&m,&B,&A,&D,&C);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&val[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
sm[i][j]=val[i][j]+sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];
}
}
for(int i=B;i<=n;++i){
for(int j=A;j<=m;++j){
b[i][j]=sm[i][j]-sm[i-B][j]-sm[i][j-A]+sm[i-B][j-A];
// printf("%d ",b[i][j]);
}
// puts("");
}
for(int i=D;i<=n;++i){
for(int j=C;j<=m;++j){
a[i][j]=sm[i][j]-sm[i-D][j]-sm[i][j-C]+sm[i-D][j-C];
// printf("%d ",a[i][j]);
}
// puts("");
}
int ans=0;
for(int i=D+1;i<n;++i){
for(int j=C+1;j<m;++j){
// printf("%d %d\n",i,j);
while(!q[j].empty()&&a[q[j].back()][j]>a[i][j]){q[j].pop_back();}
q[j].push_back(i);
while(!q[j].empty()&&i-q[j].front()>B-D-2){q[j].pop_front();}
}
while(!qq.empty()){qq.pop_back();}
for(int j=C+1;j<m;++j){
while(!qq.empty()&&a[q[qq.back()].front()][qq.back()]>a[q[j].front()][j]){qq.pop_back();}
qq.push_back(j);
while(!qq.empty()&&j-qq.front()>A-C-2){qq.pop_front();}
if(!qq.empty()&&i>=B-1&&j>=A-1){ans=max(ans,b[i+1][j+1]-a[q[qq.front()].front()][qq.front()]);}
}
}
printf("%d\n",ans);
}
int main(){
init();
return 0;
}P1083 NOIP2012 借教室
本质上是区间减区间最小值。
考虑到先操作再询问，差分加前缀和即可。
对于题目要求的那个答案，我们找到第一个不合法的点，然后枚举每一个询问和它比较即可
复杂度O(n+m)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1000005;
ll a[N],val[N];
int qx[N],ql[N],qr[N];
int n,m;
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%lld",&a[i]);
}
for(int i=1;i<=m;++i){
scanf("%d%d%d",&qx[i],&ql[i],&qr[i]);
val[ql[i]]+=qx[i],val[qr[i]+1]-=qx[i];
}
int loc=0;
for(int i=1;i<=n;++i){
val[i]+=val[i-1];
if(val[i]>a[i]){
loc=i;
break;
}
}
if(!loc){
puts("0");
return;
}
ll cnt=0;
for(int i=1;i<=m;++i){
if(ql[i]<=loc&&qr[i]>=loc){
if(cnt+qx[i]>a[loc]){
puts("-1");
printf("%d\n",i);
return;
}else{
cnt+=qx[i];
}
}
}
}
int main(){
init();
return 0;
}
lp3313 SDOI2014 旅行
虽然这一题被划在主席树下面，但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链，建很多棵线段树，每棵线段树表示这条链上某种颜色的情况，然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多（这可能是为什么这题会被放在主席树下面），但是可能存在很多细节。
另：我的线段树区间查询写成依次单点查询，居然跑到了1.2s，让我一度以为是我常数问题…甚至差点卡进去了。精彩。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline int rd(){
char ch=getchar();int r=0;
while(!isdigit(ch)){ch=getchar();}
while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
return r;
}
const int N=100005;
inline int Max(int A,int B){
return A>B?A:B;
}
inline void Swap(int &A,int &B){
A^=B^=A^=B;
}
struct ee{
int v;
int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
inline void add(int U,int V){
Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==fa[X]){continue;}
fa[e[i].v]=X;
dfs0(e[i].v);
if(sz[e[i].v]>sz[sn[X]]){
sn[X]=e[i].v;
}
sz[X]+=sz[e[i].v];
}
}
inline void dfs1(int X){
dfn[X]=++cnt;
if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
tp[e[i].v]=e[i].v;dfs1(e[i].v);
}
}
#define MID ((L+R)>>1)
struct Node{
int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
if(!NW){NW=++tcnt;}
if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
if(A>R||B<L||!X){return 0;}
if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R
return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
if(A>R||B<L||!X){return 0;}
if(A<=L&&B>=R){return tr[X].sm;}
return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
chg(rt[X],1,n,P,V);
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
val[i]=rd(),clr[i]=rd();
}
int u,v;
for(int i=1;i<n;++i){
u=rd(),v=rd();
add(u,v);
}
sz[0]=0;fa[1]=0;
dfs0(1);
tp[1]=1;
dfs1(1);
for(int i=1;i<=n;++i){
ADD(clr[i],dfn[i],val[i]);
}
char ch[10];
int x,y,c;
for(int i=1;i<=m;++i){
std::cin>>ch+1;
switch(ch[2]){
case 'C':{
x=rd(),y=rd();
ADD(clr[x],dfn[x],0);
ADD(clr[x]=y,dfn[x],val[x]);
break;
}
case 'W':{
x=rd(),y=rd();
ADD(clr[x],dfn[x],val[x]=y);
break;
}
case 'S':{
x=rd(),y=rd();
int RT=0;c=clr[x];
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
x=fa[tp[x]];
}
if(dep[x]<dep[y]){Swap(x,y);}
RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
printf("%d\n",RT);
break;
}
case 'M':{
x=rd(),y=rd();
int RT=0;c=clr[x];
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
x=fa[tp[x]];
}
if(dep[x]<dep[y]){Swap(x,y);}
RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
printf("%d\n",RT);
break;
}
}
}
}
int main(){
// freopen("33132.in","r",stdin);
// freopen("33132.ans","w",stdout);
init();
return 0;
}
lp3285 SCOI2014 方伯伯的OJ
题目要求维护一个编号序列和一个排名序列，并支持四种操作：
1.按照编号修改编号，并返回该编号的排名。
2.将一个节点的排名提升到第一个。
3.将一个节点的排名降低到最后一个。
4.查询某个排名的编号。
很显然是用Splay维护排名，然后开一个数组存编号咯。
然而我们观察到这一题的数据范围是n<=10^8，那么用上述的方法显然会MLE。
故而我们考虑一个Splay节点「真的维护」一个区间。然后每一次要用到一个新的点就把原有的区间剖开。
而数组存编号也就很套路地换成map存编号。
【冬天来了手都在发抖啊】
续：这一题是我在190103的时候写完的，然而直到191003我才调出来。期间经过了十个月。
调试的突破性进展来自于对调试工具的学习使用，这使得我在巨大数据的情况下得以想办法调试。
我首先发现了size发生了错误，进而发现某个节点的size不等于其两孩子的大小之和加上它本身的大小。然后，经由此处，我发现有个节点的相邻节点是一个大小为空的节点，进而发现这个节点在被分配下标之前就被访问了。
最终，我注意到它第一次出现所相接的节点，并发现这个数事实上是一个标号。
紧接着我就顺利地调出另一个错，并通过了此题。
注意点：
1.对于空节点的情况一定要认真考虑，因为如果空节点操作不慎的话很可能会导致一些莫名其妙的错误。
2.要注意适时更新节点。
3.千万不要搞混「标号」和「排名」！！！！！！
4.如果一个点本来就是排名最后的点而要移到排名最后，有可能会出错。
#include<iostream>
#include<cstdio>
#include<map>
#define error(X) printf("ERROR: %d",X)
#define debug(P) printf("(%d):%d,%d,sn:[%d,%d],FA:%d,SZ:%d\n",P,tr[P].l,tr[P].r,tr[P].sn[0],tr[P].sn[1],tr[P].fa,tr[P].sz);
bool bo=0;
class Splay{
public:
class Node{
public:
int l;
int r;
int sz;
int sn[2];
int fa;
inline void set(int L,int R,int FA){
l=L,r=R,fa=FA,sz=R-L+1,sn[0]=sn[1]=0;
}
};
//i表示mp[i]这个节点的右端点的标号。
std::map<int,int> mp;
Node tr[400005];
int cnt,rt;
//寻找当前节点与父亲的关系。
inline int fndD(int X){
return tr[tr[X].fa].sn[1]==X;
}
//更新当前节点。
inline void updt(int X){
tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].r-tr[X].l+1;
// if(X==10619&&tr[X].sz<=30){prnt(tr[X].fa);}
}
//旋转套装。
inline void splayOne(int X){
if(!X){return;}
int D=fndD(X),D2=fndD(tr[X].fa);
// if(X==65505||tr[X].fa==65505||tr[tr[X].fa].sn[D^1]==65505){
// puts("FKFKFK");
// printf("X");debug(X);
// printf("FA");debug(tr[X].fa);
// printf("BR");debug(tr[tr[X].fa].sn[D^1]);
// }
tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].sn[D^1]].fa;
tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
updt(tr[X].sn[D^1]),updt(X);
}
inline void splayTwo(int X){
// if(bo&&X==38190){debug(X);}
int D=fndD(X),D2=fndD(tr[X].fa);
tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
}
inline void splayRnw(int X){
while(tr[X].fa){splayTwo(X);}
rt=X;
}
// inline void splayRnw(int X){
// while(tr[X].fa){
// int F=tr[X].fa,FF=tr[tr[X].fa].fa;
// if(!FF)
// }
// }
//找到排名为X的元素。
inline int fnd(int X){
int P=rt;
while(P){
if(X>tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1){
X-=tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1;
P=tr[P].sn[1];
}else if(X>tr[tr[P].sn[0]].sz){
X-=tr[tr[P].sn[0]].sz;
splayRnw(P);
// debug(P);
return tr[P].l+X-1;
}else{
P=tr[P].sn[0];
}
}
return -1;
}
//开一个新节点，以X为它的父亲。
inline int nwlc(int X,int L,int R){
int P=++cnt;
// if(P==65505){
// printf("START:");
// debug(P);
// }
tr[P].set(L,R,X);
return P;
}
//将编号为X的节点单独弄成一个新的节点，然后将它的两个子节点接到它的左右，并更改相应的编号的映射
inline int split(int P,int X){
if(tr[P].l==tr[P].r){return P;}
if(P==-1){return error(192600404),192600404;}
if(X>tr[P].l){
int L=tr[P].sn[0];
L?(cut(L),0):(tr[0].fa=0);
tr[P].sn[0]=nwlc(P,tr[P].l,X-1);
L?(cnnct(L,tr[P].sn[0],0),0):0;
mp[X-1]=tr[P].sn[0];
// updt(tr[P].sn[0]);
}
if(X<tr[P].r){
int R=tr[P].sn[1];
R?(cut(R),1):(tr[0].fa=0);
tr[P].sn[1]=nwlc(P,X+1,tr[P].r);
R?(cnnct(R,tr[P].sn[1],1),1):1;
mp[tr[P].r]=tr[P].sn[1];
// updt(tr[P].sn[1]);
}
tr[P].l=tr[P].r=X;mp[X]=P;
updt(P);
return P;
}
inline int fndMn(int X){
int P=X,FP=tr[X].fa;
while(P){
FP=P;
P=tr[P].sn[0];
}
return FP;
}
inline int fndMx(int X){
int P=X,FP=tr[X].fa;
while(P){
FP=P;
P=tr[P].sn[1];
}
return FP;
}
inline void cut(int X){
int D=fndD(X);
tr[tr[X].fa].sn[D]=0,tr[X].fa=0;
}
inline void cnnct(int X,int Y,int D){
tr[Y].sn[D]=X,tr[X].fa=Y;
updt(Y);
}
inline void prnt(int X,int dep=0){
if(!X){return;}
for(int i=1;i<=dep;++i){
printf(" ");
}debug(X);
prnt(tr[X].sn[0],dep+1);
prnt(tr[X].sn[1],dep+1);
}
public:
inline int CHANGE(int X,int Y){
int P=mp.lower_bound(X)->second;
P=split(P,X);
tr[P].l=tr[P].r=Y;
mp[Y]=P;
splayRnw(P);
return tr[tr[P].sn[0]].sz+1;
}
inline int LST(int X){
int P=mp.lower_bound(X)->second;
P=split(P,X);
splayRnw(P);
int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
if(!L){
return RT;
}
R?(R=fndMn(R),cut(L),cnnct(L,R,0),splayRnw(L)):(cut(L),cnnct(L,P,1));//此处P写成X,调了我一年。
return RT;
}
inline int RST(int X){
int P=mp.lower_bound(X)->second;
P=split(P,X);
splayRnw(P);
int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
if(!R){
return RT;
}
L?(L=fndMx(L),cut(R),cnnct(R,L,1),splayRnw(R)):(cut(R),cnnct(R,P,0));
return RT;
}
inline int ARNK(int X){
return fnd(X);
}
//初始化。
inline void INIT(int N){
cnt=1;
rt=1;
tr[1].set(1,N,0);
mp[N]=1;
}
};
/*
Error:
192600404: 指定的节点不存在。
192600500: 切割的节点不是区间节点。
*/
int n,m;
Splay T;
void init(){
int code=0;
scanf("%d%d",&n,&m);
T.INIT(n);
int op,x,y;
for(int i=1;i<=m;++i){
scanf("%d",&op);
switch(op){
case 1:{
scanf("%d%d",&x,&y);
x-=code,y-=code;
printf("%d\n",code=T.CHANGE(x,y));
// if(code==95204&&i>=80000){
// puts("fk1");
// printf("%d\n",x);
// return;
// }
break;
}
case 2:{
scanf("%d",&x);
x-=code;
printf("%d\n",code=T.LST(x));
break;
}
case 3:{
scanf("%d",&x);
x-=code;
printf("%d\n",code=T.RST(x));
break;
}
case 4:{
scanf("%d",&x);
x-=code;
printf("%d\n",code=T.ARNK(x));
break;
}
}
// printf("CORESIZE:%d\n",T.tr[54567].sz);
}
}
int main(){
// freopen("input1.in","r",stdin);
// freopen("output1.out","w",stdout);
init();
return 0;
} lp4768 NOI2018 归程
克鲁斯卡尔重构树模板题。
我们发现，这一题可以拆成两个步骤。第一个步骤，是找到所有u可以通过共享单车达到的点；第二个步骤，是找到这些点中到原点最小的点的距离。
我们容易发现，第一个步骤和长度无关，第二个步骤和海拔无关。
首先考虑第一个步骤。
我们建出一棵克鲁斯卡尔重构树——克鲁斯卡尔重构树是这样的一个数据结构：当你使用克鲁斯卡尔算法建最小/最大生成树的时候，每一次合并，你新建一个节点p，这个点的点权是这一次合并通过的边的边权，然后将即将合并的两个点的根节点合并到p下。这样我们构造出了一棵二叉树，其中所有叶子节点是原图上的节点。
克鲁斯卡尔重构树满足一些有意义的性质。
不妨以这题为例，我们构造一棵最大生成树，那么两点之间的lca的点权就是这两个点之间路径中边权最大的值。换句话说，从u在d的降水下可以到的节点，就是所有和u的lca的点权大于等于d的节点。考虑到这是一棵最大生成树，每个点的父亲节点的点权不会大于这个节点。这也就意味着，我们需要找到u的最高的祖先，使得这个祖先的点权大于等于d。不妨称这个祖先为w，那么w的子树的所有叶子节点，就是u在d的降水下能抵达的节点。
于是，我们求出了第一个步骤的解。
然后我们考虑第二个步骤的解。考虑到这是一张无向图，我们先求出1号节点到所有节点的距离，然后把这些值赋到叶子节点上，不妨称它为『距离权值』。因为我们每一次求min必然是求「某个点的子树中所有叶子节点的『距离权值』的最小值」，那么就可以进行树形dp，把这个最小值的信息直接记录到每个虚拟节点上。
这就做完了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=800005,M=800005;
const int INF=0x3f3f3f3f;
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int w;
int a;
int nxt;
}e[M<<1];
int h[N],et=0;
inline void Eadd(int U,int V,int W,int A){
e[++et]=(ee){V,W,A,h[U]};
h[U]=et;
}
inline void add(int U,int V,int W,int A){
Eadd(U,V,W,A);
Eadd(V,U,W,A);
}
struct tee{
int v;
int nxt;
}te[N<<1];
int g[N],tet=0;
inline void tEadd(int U,int V){
te[++et]=(tee){V,g[U]};
g[U]=et;
}
inline void tadd(int U,int V){
tEadd(U,V);
tEadd(V,U);
}
struct data{
int u;int v;int a;
}lst[M];
inline bool cmp(const data &A,const data &B){
return A.a>B.a;
}
int ff[N],f[N][20];
inline int fa(int X){
return ff[X]==X?ff[X]:ff[X]=fa(ff[X]);
}
int val[N];
int n,m,cnt,rt;
inline void uni(int X,int Y){
X=fa(X),Y=fa(Y);
tadd(ff[X],cnt);tadd(ff[Y],cnt);
ff[X]=ff[Y]=cnt;
}
inline void kruskal(){
cnt=n;
for(int i=1;i<=m;++i){
if(fa(lst[i].u)==fa(lst[i].v)){
continue;
}
val[++cnt]=lst[i].a;
uni(lst[i].u,lst[i].v);
if(cnt==n*2-1){
break;
}
}
rt=fa(1);
}
int dis[N],vis[N];
struct cmp2{
inline bool operator()(int A,int B){
return dis[A]>dis[B];
}
};
priority_queue< int,vector<int>,cmp2 > q;
inline void dij(){
for(int i=2;i<=n*2;++i){
dis[i]=INF;vis[i]=0;
}
vis[1]=1,dis[1]=0;
q.push(1);
int p;
while(!q.empty()){
p=q.top();q.pop();vis[p]=0;
for(int i=h[p];i;i=e[i].nxt){
if(dis[e[i].v]>dis[p]+e[i].w){
dis[e[i].v]=dis[p]+e[i].w;
if(!vis[e[i].v]){
q.push(e[i].v);
}
}
}
}
}
inline void dfs0(int X){
for(int i=g[X];i;i=te[i].nxt){
if(te[i].v==f[X][0]){
continue;
}
// printf("%d %d\n",X,te[i].v);
f[te[i].v][0]=X;
for(int j=1;j<=18;++j){
f[te[i].v][j]=f[f[te[i].v][j-1]][j-1];
}
dfs0(te[i].v);
dis[X]=Min(dis[X],dis[te[i].v]);
}
}
inline int qry(int X,int D){
for(int i=18;i>=0;--i){
if(val[f[X][i]]>D){
X=f[X][i];
}
}
return dis[X];
}
void init(){
scanf("%d%d",&n,&m);
et=tet=0;
for(int i=1;i<=n*2;++i){
g[i]=h[i]=0;
}
int u,v,w,a;
for(int i=1;i<=m;++i){
scanf("%d%d%d%d",&u,&v,&w,&a);
add(u,v,w,a);
lst[i]=(data){u,v,a};
}
std::sort(lst+1,lst+1+m,cmp);
for(int i=1;i<=n*2;++i){
ff[i]=i;val[i]=INF;
}
kruskal();
dij();
dfs0(rt);
// for(int i=1;i<=rt;++i){
// printf("%d ",dis[i]);
// }
// puts("");
int Q,K,S,lans=0,x,d;
scanf("%d%d%d",&Q,&K,&S);
for(int i=1;i<=Q;++i){
scanf("%d%d",&x,&d);
x=(x+lans*K-1)%n+1;d=(d+lans*K)%(S+1);
printf("%d\n",lans=qry(x,d));
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
init();
}
return 0;
}
lp3168 CQOI2015 任务查询系统
观察题面，我们发现这是一道变态题：区间加点，单点查询第k大，强制在线——这tm不是变态题么！别的不说，权值怎么离散化我都不会。
仔细一看，真的是这样么？
我们发现，先是m个修改，后面再跟着n个询问！这意味着什么？这意味着所谓的区间修改事实上是fake的，因为我们事实上只要对最后一个版本进行询问。
经验上，多次区间修改后求单点值，我们使用差分+前缀和来维护。在这里同样是生效的，只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存，比如说Vector或者手写邻接表。
那就是主席树裸题了。
注意：每一次修改的时候修改的仅仅是L和R+1两个点，但是这并不是正确的！在把修改排序之后，每一个修改是从它的上一个点复制版本，但上一个版本可能并没有任何修改，这也就意味着，上一个版本可能是空的！这就完全不是前缀和了。
应当如何做呢？每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改，也仍然能保持它的性质。
另外，离散化的时候不应该把点离散化在一起。在这里，把值相同的点离散化到不同的位置并不会影响答案。事实上，如果把值相同的点离散化到相同的位置，反而会更麻烦。这是因为如果离散化到相同的位置，那么这三个点在线段树上就存在同一个点里了。这时候，倘若这个点的大小为3，而你需要查询前2大的和，你就无法处理了。这平白增加了实现的复杂度。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=100005;
inline int Abs(int X){
return X>0?X:-X;
}
#define MID ((L+R)>>1)
vector<int> lst[N];
struct data{
int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
private:
class Node{
public:
int l;int r;int sz;ll sm;
}tr[N*160];
int cnt,rt[N];
inline void bld(int LST,int &NW,int L,int R,ll V){
NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
if(L==R){return;}
Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
}
inline ll qry(int X,int L,int R,ll V){
ll RT=0;
while(L<R){
// printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
}
RT+=tr[X].sm;
return RT;
}
inline void prnt(int X){
if(!X){
return;
}
printf("%d|%lld ",tr[X].sz,tr[X].sm);
prnt(tr[X].l);prnt(tr[X].r);
}
public:
inline void ADD(int X,ll V){
int nw;
if(!rt[X]){
bld(rt[X-1],rt[X],1,100000,V);
}else{
bld(rt[X],nw,1,100000,V);
rt[X]=nw;
}
}
inline ll QRY(int X,int V){
// printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
}
inline void RNW(int X){
if(!rt[X]){
rt[X]=rt[X-1];
}
}
inline void PRNT(int X){
prnt(rt[X]);
}
inline void prpr(){
cnt=0;
tr[0].sz=tr[0].sm=0;
for(int i=1;i<=n;++i){
rt[i]=0;
}
}
}TR;
void init(){
TR.prpr();
scanf("%d%d",&m,&n);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
}
std::sort(a+1,a+1+m,cmp);
vl[0]=0,a[0].val=0;
for(int i=1;i<=m;++i){
vl[i]=vl[i-1]+1;
loc[vl[i]]=a[i].val;
}
for(int i=1;i<=m;++i){
lst[a[i].l].push_back(vl[i]);
lst[a[i].r+1].push_back(-vl[i]);
}
for(int i=1;i<=n;++i){
TR.RNW(i);
for(int j=0;j<lst[i].size();++j){
TR.ADD(i,lst[i][j]);
}
}
int x,a,b,c,v;ll lans=1;
for(int i=1;i<=n;++i){
scanf("%d%d%d%d",&x,&a,&b,&c);
v=(1ll*lans*a+b)%c+1;
printf("%lld\n",lans=TR.QRY(x,v));
}
}
int main(){
init();
return 0;
}lp3302 SDOI2013 森林
我们发现，树上的链上第k大是可以使用主席树来维护的。对于每一个节点，我们从它的父亲复制一个版本，然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树，我们可能可以想到用LCT来维护。但是代码难度太高，而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作，也就是说，每一次，我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树，我们暴力更新其中的每一个节点。于是可以证明，每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意：主席树的L，R本身就是节点位置；合并的时候要记得更新小树的根节点；返回的值是第k大的值而非第k大的排名因而要逆离散化。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
const int N=80005;
struct data{
int id;
int val;
}a[N];
inline bool cmp(const data &A,const data &B){
return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
return A.id<B.id;
}
struct ee{
int v;
int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
inline void add(int U,int V){
Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
private:
class Node{
public:
int l;int r;int sz;
};
Node tr[30000000];
int cnt,rt[N];
inline void bld(int LST,int &NW,int L,int R,int V){
NW=++cnt;tr[NW].sz=tr[LST].sz+1;
if(L==R){return;}
V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
}
inline int qry(int A,int B,int C,int D,int L,int R,int V){
while(L<R){
// printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
}
return L;
}
inline void prnt(int X){
if(!X){
return;
}
prnt(tr[X].l);
prnt(tr[X].r);
printf("%d ",tr[X].sz);
}
public:
inline void ADD(int LST,int VER,int V){
bld(rt[LST],rt[VER],1,80000,V);
}
inline int QRY(int A,int B,int C,int D,int V){
return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
}
inline void prpr(){
cnt=0;
}
inline void pt(int X){
prnt(rt[X]);
}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
// printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
vis[X]=sz[X]=1;
for(int i=h[X];i;i=e[i].nxt){
if(vis[e[i].v]){
continue;
}
fa[e[i].v][0]=X;
dep[e[i].v]=dep[X]+1;
for(int j=1;j<=18;++j){
fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
}
TR.ADD(X,e[i].v,a[e[i].v].val);
dfs0(e[i].v);
sz[X]+=sz[e[i].v];
}
}
inline void dfs1(int X){
vis[X]=0;
for(int i=h[X];i;i=e[i].nxt){
if(!vis[e[i].v]){
continue;
}
dfs1(e[i].v);
}
}
inline int szq(int X){
for(int i=18;i>=0;--i){
if(fa[X][i]!=0){
X=fa[X][i];
}
}
return sz[X];
}
inline void uni(int X,int Y){
int SZ=szq(X);
dfs1(X);
add(X,Y);
fa[X][0]=Y;
dep[X]=dep[Y]+1;
TR.ADD(Y,X,a[X].val);
for(int i=1;i<=18;++i){
fa[X][i]=fa[fa[X][i-1]][i-1];
}
int RT=X;
for(int i=18;i>=0;--i){
if(fa[RT][i]){
RT=fa[RT][i];
}
}
sz[RT]+=SZ;
dfs0(X);
}
inline int lca(int X,int Y){
if(dep[X]<dep[Y]){
X^=Y^=X^=Y;
}
for(int i=18;i>=0;--i){
if(dep[fa[X][i]]>=dep[Y]){
X=fa[X][i];
}
}
if(X==Y){
return X;
}
for(int i=18;i>=0;--i){
if(fa[X][i]!=fa[Y][i]){
X=fa[X][i],Y=fa[Y][i];
}
}
return fa[X][0];
}
int n,m,q,tid;
void init(){
scanf("%d",&tid);
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i){
scanf("%d",&a[i].val);
a[i].id=i;
}
std::sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;++i){
loc[i]=a[i].val;
}
for(int i=1;i<=n;++i){
if(a[i].val!=a[i-1].val){
a[i].val=a[i-1].val+1;
}else{
a[i].val=a[i-1].val;
}
}
std::sort(a+1,a+1+n,cmp2);
int u,v;
for(int i=1;i<=m;++i){
scanf("%d%d",&u,&v);
add(u,v);
}
TR.prpr();
for(int i=1;i<=n;++i){
if(!vis[i]){
dep[i]=1;
TR.ADD(0,i,a[i].val);
dfs0(i);
}
}
// for(int i=1;i<n;++i){
// printf("%d:",i);
// TR.pt(i);
// puts("");
// }
int lans=0,x,lc;
char ch[10];
for(int i=1;i<=q;++i){
cin>>ch+1;
switch(ch[1]){
case 'Q':{
scanf("%d%d%d",&u,&v,&x);
u^=lans,v^=lans,x^=lans;
lc=lca(u,v);
// printf("\t\t\t%d %d %d\n",u,v,x);
printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
break;
}
case 'L':{
scanf("%d%d",&u,&v);
u^=lans,v^=lans;
// printf("\t\t\t%d %d\n",u,v);
if(szq(u)>szq(v)){
u^=v^=u^=v;
}
uni(u,v);
break;
}
}
}
}
int main(){
init();
return 0;
}lp5395 【模板】第二类斯特林数·行
第二类斯特林数，指的是一组表示「将n个不同的元素划分为m个非空不相交集的方案数」的组合数。有时写作\(S(n,m)\)或\(\left\{\begin{matrix}n\\m\end{matrix}\right\}\)
从题意来看，我们可以容易地想到一个递推方案：每个新的元素，可以为它新开一个集合，或者放到已有的任何一个集合里面。所以我们得到一个递推式：
$$S(n,m)=S(n-1,m-1)+m*S(n-1,m)$$
然后问题是怎么求值。
首先我们有一个式子，我们称之为二项式反演的通项式。
$$ f(n)=\sum_{i=0}^nC_{n}^{i}g(n) \Leftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}C_{i}{n}f(n)$$
举个例子：
$$\begin{matrix} f_{1}&=&g_{1}\\f_{2}&=&g_{1}&+&g_{2}\\f_{3}&=&g_{1}&+&2*g_{2}&+&g_{3}\\f_{4}&=&g_{1}&+&3*g_{2}&+&3*g_{3}&+&g_{4} \end{matrix}$$
由此可得：
$$\begin{matrix} g_{1}&=&f_{1}\\g_{2}&=&f_{2}&-&f_{1}\\g_{3}&=&f_{3}&-&2*g_{2}&-&g_{1}\\&=&f_{3}&-&2*f_{2}&+&f_{1}\\g_{4}&=&f_{4}&-&3*g_{3}&-&3*g_{2}&-&g_{1}\\&=&f_{4}&-&3*f_{3}&-&3*g_{2}&-&4*g_{1}\\&=&f_{4}&-&3*f_{3}&+&3*f_{2}&-&f_{1} \end{matrix}$$
然后我们考虑\(m^n\)的组合意义，也就是，将\(n\)个不同的球，放到\(m\)个不同的盒子（可以有空盒）的方案数。
我们不妨枚举有装东西的盒子的个数。令它为\(i\)，那么选取这些盒子的方案数即是\(C_{m}^{i}\)。
选取了盒子之后，问题就转化为了将\(n\)个不同物品装到\(m\)个不同盒子里，使得每个盒子非空。这就相当于，将\(n\)个不同物品装到\(m\)个相同盒子里，使得每个盒子非空的方式——也就是\(S(n,m)\)，乘上盒子的排列顺序——也就是\(m!\)。
形式化的说，就是：
$$m^n=\sum_{i=0}^{m}S(n,i)i!C_{m}^{i}$$
我们发现这个式子的形式符合二项式反演的通项式。
因而我们将\(m^n\)作为\(f\)，将\(S(n,i)i!\)作为\(g\)。
那么反演得到：
$$S(n,m)=\frac{1}{m!}\sum_{i=0}^{m}(-1)^{m-i}i^nC_{m}^{i}$$
考虑\(C_{m}^{i}=\frac{m!}{i!(m-i)!}\)，我们可以将上式化简得到：
$$S(n,m)=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
于是我们有：
$$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$$
考虑函数卷积的本质，对于卷积\(f=gu\)，其本质是： $$f(n)=\sum_{i=0}^{n}g(i)u(n-i)$$ 因而，我们发现，上式本质上就是： $$\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum_{i=0}^{m}\frac{(-1)^{m-i}}{(m-i)!}*\frac{i^n}{i!}$$
上一个NTT卷积一下就好了。
#include<iostream>
#include<cstdio>
#define Swap(A,B) (A^=B^=A^=B)
const long long P=167772161;
const long long g0=3,gi=55924054;
int L=1,R[1<<21|1];
long long invL;
inline int pw(int A,int X){
long long BS=A,RT=1;
while(X){
if(X&1){
RT=RT*BS%P;
}
BS=BS*BS%P;
X>>=1;
}
return RT;
}
inline void prpr(int LEN){
int B=0;
while(L<=LEN){
L<<=1;
++B;
}
invL=P-(P-1)/L;
for(int i=0;i<L;++i){
R[i]=R[i>>1]>>1|(i&1)<<(B-1);
}
}
inline void FNTT(int *A,int typ){
for(int i=0;i<L;++i){
if(R[i]<i){
Swap(A[R[i]],A[i]);
}
}
int gn,g,X,Y,M;
for(int i=2;i<=L;i<<=1){
M=i>>1;
gn=pw(~typ?g0:gi,(P-1)/i);
for(int j=0;j<L;j+=i){
g=1;
for(int k=0;k<M;++k,g=1ll*g*gn%P){
X=A[j+k],Y=1ll*g*A[M+j+k]%P;
A[j+k]=(X+Y)%P,A[M+j+k]=(X-Y)%P;
}
}
}
}
int n,a[1<<21|1],b[1<<21|1],inv[1<<21|1];
void init(){
scanf("%d",&n);
prpr(n+1<<1);
inv[0]=inv[1]=1;
for(int i=2;i<=n;++i){
inv[i]=1ll*(P-P/i)*inv[P%i]%P;
}
for(int i=1;i<=n;++i){
inv[i]=1ll*inv[i-1]*inv[i]%P;
}
for(int i=0;i<=n;++i){
a[i]=1ll*pw(-1,i)*inv[i]%P;
b[i]=1ll*pw(i,n)*inv[i]%P;
}
FNTT(a,1);
FNTT(b,1);
for(int i=0;i<L;++i){
a[i]=1ll*a[i]*b[i]%P;
}
FNTT(a,-1);
for(int i=0;i<=n;++i){
printf("%d ",1ll*(a[i]+P)*invL%P);
}
}
int main(){
init();
return 0;
}lp2501 HAOI2006 数字序列
我们分别考虑一二问。
对于第一问，我们思考一个子序列是合法的「不用修改」的子序列的充要条件。
容易想到的，这个条件是：
$$ \forall i,j\in S, i=j-i$$
自然语言化地说，就是，对于这个不用修改的子序列中的任意两个元素，它们的值的差距至少要大于它们间的元素个数，这样才能放得下它们中间的元素。
移项，我们得到：
$$a_j-j>=a_i-i$$
所以，我们令\(b_i=a_i-i\)，那么第一问中不用修改的个数就是\(b\)的最长不下降子序列长度。
对于第二问，首先，它可以被转化为「最小修改代价求\(b\)单调不减」。
我们有一个结论：相邻两关键点\(i,j\)间一定可以找到一条分界线，使得线左端的所有点变化成\(b_i\)，右端所有点变化成\(b_j\)会最优。
这是如何证明的呢？
首先，我们知道，\(i,j\)之间的任意一个点，它的值必然要小于\(b_i\)或者大于\(b_j\)，否则选取这个点只会让答案更优。
然后，我们尝试进行反证。如果有一个点修改以后位于中间，并且它可以被修改到某一边，那么显然修改到某一边之后答案会更小。
如果将分界线定在某处，会使得某些点与它们的最优处于的边不相同，那么考虑这些点与分界点之间的其他点的数量。
如果其他点的数量小于这些点，那么不妨把这些点修改后的位置换到另一边，这样答案就变小了点数差*上下两边距离。
否则，不如不修改。
所以我们证明了这个结论。
然后是关于时间复杂度的。可以证明，在序列随机的情况下，最长不下降子序列的期望长度是logn级别的。（我不会证，也找不到文章。求大佬教教我）
注意：要提前把\(b_0\)设成\(-INF\)，并在末尾插入一个\(INF\)的点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=35005;
const int INF=0x3f3f3f3f;
inline ll Abs(ll X){
return X>=0?X:-X;
}
inline ll Min(ll A,ll B){
return A<B?A:B;
}
int n,a[N],b[N],nm[N];
ll f[N],sm1[N],sm2[N];
struct ee{
int v;
int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
b[i]=a[i]-i;
}
int cnt=0,nw;
b[0]=-INF;f[0]=-INF;
b[++n]=INF;
for(int i=1;i<=n;++i){
if(b[i]>=f[cnt]){
f[++cnt]=b[i];
nm[i]=cnt;
}else{
nw=upper_bound(f+1,f+cnt,b[i])-f;
f[nw]=b[i];
nm[i]=nw;
}
}
printf("%d\n",n-cnt);
for(int i=n;i>=0;--i){
add(nm[i],i);
f[i]=INF;
}
f[0]=0;
int v;
for(int i=1;i<=n;++i){
for(int j=h[nm[i]-1];j;j=e[j].nxt){
v=e[j].v;
if(v>i||b[v]>b[i]){
continue;
}
sm1[v]=0;
for(int k=v+1;k<=i;++k){
sm1[k]=sm1[k-1]+Abs(b[k]-b[v]);
}
sm2[i-1]=0;
for(int k=i-2;k>=v;--k){
sm2[k]=sm2[k+1]+Abs(b[k+1]-b[i]);
}
for(int k=v;k<i;++k){
f[i]=Min(f[i],f[v]+sm1[k]+sm2[k]);
}
}
}
printf("%lld\n",f[n]);
}
int main(){
init();
return 0;
}
lp2515 HAOI2010 软件安装
简单的tarjan缩点+树形背包DP。
考虑N<=100，M<=500，只需要设f[i][j]表示第i个点，已用j的容量。
然后直接DP即可。
特别地，由于如果某一个点的子树中的点被选中了，这个点也要被选中，所以我们在计算每个点的时候，一定要将这个点加进去。
然后仔细看看这道题，发现它不保证没有环！
这下完蛋了，咋做啊？
考虑到这个环要么都选，要么都不选，所以可以先用tarjan找环，把找环后的点拿来dfs。
然后我们考虑一个性质：如果存在环，那么这个环缩成的点一定是某一棵树的树根。
所以我们不妨计算每一个点的入度，然后将入度为0的点连向虚点0。这样只需要一次DP。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline int Max(int A,int B){
return A>B?A:B;
}
inline int Min(int A,int B){
return A<B?A:B;
}
struct ee{
int v;
int nxt;
}e[505];
int h[505],g[505],et=0;
inline void add(int *H,int U,int V){
e[++et]=(ee){V,H[U]};
H[U]=et;
}
int n,m,f[505][505],w[505],v[505],ww[505],val[505],d[505],in[505];
int vis[505],clr[505],dfn[505],lw[505],cnt=0,ccnt=0,st[505],tp=0;
inline void dfs0(int X){
vis[X]=1,dfn[X]=lw[X]=++cnt;
st[++tp]=X;
for(int i=g[X];i;i=e[i].nxt){
if(!dfn[e[i].v]){
dfs0(e[i].v);lw[X]=Min(lw[X],lw[e[i].v]);
}else if(vis[e[i].v]){
lw[X]=Min(lw[X],dfn[e[i].v]);
}
}
if(dfn[X]==lw[X]){
++ccnt;
while(st[tp+1]!=X){
clr[st[tp]]=ccnt;
val[ccnt]+=v[st[tp]],ww[ccnt]+=w[st[tp]];
vis[st[tp]]=0;
--tp;
}
}
}
inline void dfs1(int X){
for(int i=ww[X];i<=m;++i){
f[X][i]=val[X];
}
for(int i=h[X];i;i=e[i].nxt){
dfs1(e[i].v);
for(int j=m-ww[X];j>=0;--j){//j表示之前的子树的重量和。
for(int k=0;k<=j;++k){//k表示这棵子树的重量和。
f[X][j+ww[X]]=Max(f[X][j+ww[X]],f[e[i].v][k]+f[X][j-k+ww[X]]);
}
}
}
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
scanf("%d",&w[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&v[i]);
}
for(int i=1;i<=n;++i){
scanf("%d",&d[i]);
if(d[i]){
add(g,d[i],i);
}
}
for(int i=1;i<=n;++i){
if(!dfn[i]){
dfs0(i);
}
}
for(int i=1;i<=n;++i){
if(clr[d[i]]!=clr[i]){
add(h,clr[d[i]],clr[i]);
++in[clr[i]];
}
}
for(int i=1;i<=ccnt;++i){
if(!in[i]){
add(h,0,i);
}
}
dfs1(0);
printf("%d\n",f[0][m]);
}
int main(){
init();
return 0;
}
lp3233 HNOI2014 世界树
让我们来分析这道题。
我们很容易地可以发现，如果一个节点是末端节点，那么它肯定是由它祖先中的第一个节点管辖更优。
由此我们继续推导，可以发现，假如只有两个关键点的话，它们之间的链上一定可以找到一个分界线，使得这条分界线的一段——以及所有与链上这一端相邻的节点——放在一个关键点上，并把剩下的放在另一个关键点上。这样是最优的。
然后我们考虑有三个关键点的情况。如果有三个关键点的话，问题似乎就复杂了很多，这是因为这条分界线必须是基于三个节点共同决定的。
我们换一个思路考虑。求出三个关键点两两的LCA。那么，这一分界线就必然可以在这六个点（最多六个）两两之间的链上找到。
存在一种叫做「虚树」的数据结构。这个数据结构本质上就是将所有关键点以及关键点两两之间的LCA建成一个数。
我们如此考虑，如果有一个点是关键点，那么它向下能够管辖的点的数量就是它的子树大小减去它的所有子节点能管辖的点数之和。
它向上能够管辖的点的数量则相对比较复杂。
我们考虑每一条边，假设我们已经预处理出了虚树上每一个点相邻最近的关键点，那么，如果这条边两端的点相邻最近的关键点是相同的，那么这条边（以及和这条边相邻的所有点）都划归到那个关键点下管辖。
如果这条边两段的点相邻最近的关键点不同，则需要使用倍增来确定这条边要如何被划分成两个部分。
接下来要考虑如何确定虚树上每一个点相邻最近的关键点。
我们不妨这样考虑：一个点相邻最近的关键点如果在它的下方，那么这可以通过树形DP求得；如果在它的上方或者其他子树内呢？
显然，如果这个点的相邻最近关键点在它的上方或者和它不在同一子树内，那么它的父亲的最近关键点一定与这个点的最近关键点相同。
于是，我们不妨从上而下DP，求得这个点在上方或者不在同一子树的最近关键点。
现在我们来梳理一下这一题的思路。
首先，我们进行预处理，处理出每个点的深度和dfn。
然后，我们进行两次树形DP，求出每个点的最近关键点。
第三，我们预处理出所有「末端节点」——也就是所有「是一个虚树上节点的直接儿子且子树内没有关键点的原树上的点」。这些点的贡献可以直接统计到它们父亲的最近关键点。
最后，我们依次考虑剩下的虚树边上的点。如果两段的最近关键点相同，那么就统计到那个最近关键点。否则就进行倍增寻找答案。
顺便讲一下如何建虚树。
我们将所有关键点按照dfs序排序，然后建一个栈，代表当前正在向下延长的链。
如果当前的点与栈顶的LCA的深度小等于次栈顶，那么就说明当前点不在栈顶的子树里，也就意味着栈顶处于当前应该维护的链外。
于是，我们需要就可以将新的这个点加入虚树和栈中。
否则，就说明原来的栈顶需要被弹出，那么就处理完它应该连的边然后将它弹出。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
#define Fv2(i,X) for(int i=g[X];i;i=e[i].nxt)
using namespace std;
typedef pair<int,int> pii;
const int N=300005;
const int INF=0x3f3f3f3f;
struct ee{
int v;
int nxt;
}e[1200005];
int h[N],g[N],et=0;
inline void add(int *H,int U,int V){
e[++et]=(ee){V,H[U]};
H[U]=et;
}
int dfn[N],cnt=0,sz[N],dep[N],fa[N][20];
inline void dfs0(int X){
dfn[X]=++cnt;sz[X]=1;
Fv(i,X){
if(e[i].v==fa[X][0]){
continue;
}
fa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;
dfs0(e[i].v);
sz[X]+=sz[e[i].v];
}
}
int usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];
pii nr[N];
inline void dfs1(int X){
nr[X]=(usd[X]?pii(0,X):pii(INF,0));
Fv2(i,X){
dfs1(e[i].v);
nr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));
}
}
inline void dfs2(int X,int D,int P){
if(pii(D,P)<nr[X]){
nr[X]=pii(D,P);
}else{
D=nr[X].first,P=nr[X].second;
}
Fv2(i,X){
dfs2(e[i].v,D+dep[e[i].v]-dep[X],P);
}
}
//子节点中所有子树中有虚树上节点的点都是不可以选取的。
//我们不妨逆向考虑，枚举每一个虚树上的子节点，然后从那个节点开始倍增，一直倍增到这棵树的子节点，然后把这些子节点的子树挖掉。
inline void dfs3(int X){
ans[hr[X]=nr[X].second]+=sz[X];
Fv2(i,X){
int nw=e[i].v;
for(int j=18;j>=0;--j){
if(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){
nw=fa[nw][j];
}
}
ans[hr[X]]-=sz[up[e[i].v]=nw];
dfs3(e[i].v);
}
}
//现在剩下的末端节点就只有虚树上的节点了。
//如果子节点的dfs序大于当前节点，那么分割点就偏上；否则偏下。
inline void dfs4(int X){
Fv2(i,X){
if(hr[e[i].v]==hr[X]){
ans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];
}else{
int len=dep[hr[e[i].v]]+dep[X]-nr[X].first;
len=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));
// 这里比较的是编号！！！
int nw=e[i].v;
for(int j=18;j>=0;--j){
if(dep[fa[nw][j]]>=len){
nw=fa[nw][j];
}
}
ans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];
ans[hr[X]]+=sz[up[e[i].v]]-sz[nw];
}
dfs4(e[i].v);
}
}
inline void dfs5(int X){
up[X]=hr[X]=0;
Fv2(i,X){
dfs5(e[i].v);
}
g[X]=0;
}
inline bool cmp(int A,int B){
return dfn[A]<dfn[B];
}
inline int lca(int X,int Y){
if(dep[X]<dep[Y]){
swap(X,Y);
}
for(int i=18;i>=0;--i){
if(dep[fa[X][i]]>=dep[Y]){
X=fa[X][i];
}
}
if(X==Y){
return X;
}
for(int i=18;i>=0;--i){
if(fa[X][i]!=fa[Y][i]){
X=fa[X][i],Y=fa[Y][i];
}
}
return fa[X][0];
}
int st[N],tp=0;
void init(){
int n,Q;
scanf("%d",&n);
int u,v;
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
add(h,u,v);
add(h,v,u);
}
dep[1]=1;
dfs0(1);
for(int j=1;j<=18;++j){
for(int i=1;i<=n;++i){
fa[i][j]=fa[fa[i][j-1]][j-1];
}
}
scanf("%d",&Q);
int m,X,Y;
while(Q--){
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d",&pt[i]);
ppt[i]=pt[i],usd[pt[i]]=1;
}
sort(pt+1,pt+1+m,cmp);
st[tp=1]=pt[1];
for(int i=2;i<=m;++i){
X=pt[i],Y=lca(X,st[tp]);
while(tp>1&&dep[Y]<=dep[st[tp-1]]){
add(g,st[tp-1],st[tp]);
--tp;
}
if(Y!=st[tp]){
add(g,Y,st[tp]);st[tp]=Y;
}
st[++tp]=X;
}
while(tp>1){
add(g,st[tp-1],st[tp]);
--tp;
}
dfs1(st[1]);
dfs2(st[1],nr[st[1]].first,nr[st[1]].second);
dfs3(st[1]);
dfs4(st[1]);
ans[hr[st[1]]]+=sz[1]-sz[st[1]];
for(int i=1;i<=m;++i){
printf("%d ",ans[ppt[i]]);
}
puts("");
dfs5(st[1]);
for(int i=1;i<=m;++i){
ans[pt[i]]=0,usd[pt[i]]=0;
}
}
}
int main(){
init();
return 0;
}lp4717 【模板】快速沃尔什变换
快速沃尔什变换是一种类似于快速傅里叶变换的操作。它是用来处理子集卷积的有效工具。
我们依次考虑操作符为and or或者xor时的情况。
我们如是考虑：将一个长度为\(2^n\)的数列\(A_{0}\)和\(A_{1}\)切割成两个长度为\(2^{n-1}\)的部分，\(A_{0}\)表示下标最高位为0的数列，而\(A_{1}\)表示下标最高位1的数列。
那么，我们有很显然的and的式子：
$$ C_{0}=A_{0} * B_{0}$$ $$ C_{1}=A_{0} * B_{1} + A_{1} * B_{0} + A_{1} * B_{1}=(A_{0} + A_{1})*(B_{0} + B_{1}) – C_{0}$$
同理，我们可以得到or的式子。
$$C_{0}=A_{0} * B_{0} + A_{1} * B_{0} + A_{0} * B_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1}) -C_{1}$$ $$C_{1}=A_{1} * B_{1}$$
以及xor的式子：
$$C_{0} = A_{0} * B_{0} + A_{1} * B_{1}$$ $$C_{1} = A_{0} * B_{1} + A_{1} * B_{0}$$
我们发现，除了xor以外的式子，都是「简洁」的。
换而言之，我们可以直接以\(nlog_n\)的复杂度求得它们的答案。
现在考虑xor这个玄妙的式子。
我们发现有如下性质：
$$C_{0} + C_{1} = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$C_{0} – C_{1} = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
我们不妨令：
$$X = (A_{0} + A_{1}) * (B_{0} + B_{1})$$ $$Y = (A_{0} – A_{1}) * (B_{0} – B_{1})$$
那么
$$ C_{0} = \frac{X + Y}{2}$$ $$ C_{1} = \frac{X – Y}{2}$$
于是就做完了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=998244353;
const ll inv2=(MOD+1)>>1;
inline void fwtor(int *A,int *B,int *C,int N){
if(N==1){
C[0]=1ll*A[0]*B[0]%MOD;return;
}
int M=N>>1;
for(int i=0;i<M;++i){
A[i+M]+=A[i];A[i+M]%=MOD;
B[i+M]+=B[i];B[i+M]%=MOD;
}
fwtor(A,B,C,M);fwtor(A+M,B+M,C+M,M);
for(int i=0;i<M;++i){
C[i+M]-=C[i]-MOD;C[i+M]%=MOD;
}
}
inline void fwtand(int *A,int *B,int *C,int N){
if(N==1){
C[0]=1ll*A[0]*B[0]%MOD;return;
}
int M=N>>1;
for(int i=0;i<M;++i){
A[i]+=A[i+M];A[i]%=MOD;
B[i]+=B[i+M];B[i]%=MOD;
}
fwtand(A,B,C,M);fwtand(A+M,B+M,C+M,M);
for(int i=0;i<M;++i){
C[i]-=C[i+M]-MOD;C[i]%=MOD;
}
}
inline void fwtxor(int *A,int *B,int *C,int N){
if(N==1){
C[0]=1ll*A[0]*B[0]%MOD;return;
}
int M=N>>1,XA,YA,XB,YB;
for(int i=0;i<M;++i){
XA=(A[i]+A[i+M])%MOD,YA=(A[i]-A[i+M]+MOD)%MOD;
XB=(B[i]+B[i+M])%MOD,YB=(B[i]-B[i+M]+MOD)%MOD;
A[i]=XA,A[i+M]=YA,B[i]=XB,B[i+M]=YB;
}
fwtxor(A,B,C,M),fwtxor(A+M,B+M,C+M,M);
for(int i=0;i<M;++i){
XA=(C[i]+C[i+M])%MOD,YA=(C[i]-C[i+M]+MOD)%MOD;
C[i]=XA*inv2%MOD,C[i+M]=YA*inv2%MOD;
}
}
int n;
int a[1<<17],b[1<<17],c[1<<17],aa[1<<17],bb[1<<17];
void init(){
scanf("%d",&n);
n=1<<n;
for(int i=0;i<n;++i)scanf("%d",a+i);
for(int i=0;i<n;++i)scanf("%d",b+i);
for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
fwtor(aa,bb,c,n);
for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
fwtand(aa,bb,c,n);
for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
for(int i=0;i<n;++i)aa[i]=a[i],bb[i]=b[i],c[i]=0;
fwtxor(aa,bb,c,n);
for(int i=0;i<n;++i)printf("%d ",c[i]);puts("");
}
int main(){
init();
return 0;
}
lp2622 关灯问题II
显然，对于某个状态，按下某个按钮之后，一定会得到另一个状态。
而灯的状态最大只有\(2^10\)。
故而考虑建一张图，2^n个点，m条边，那么答案就是从0到2^n-1的最短距离。
直接BFS即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m;
queue<int> q;
int dep[1025],vis[1025];
int a[15],b[105],c[105];
inline int bfs(){
for(int i=0;i<(1<<n);++i){
dep[i]=INF;
}
q.push(0);
dep[0]=0;
int p,v;
while(!q.empty()){
p=q.front();
q.pop();
vis[p]=0;
for(int i=1;i<=m;++i){
v=(p|b[i])&c[i];
if(dep[v]>dep[p]+1){
dep[v]=dep[p]+1;
if(!vis[v]){
q.push(v);
vis[v]=1;
}
}
}
}
return (dep[(1<<n)-1]^INF)?dep[(1<<n)-1]:-1;
}
void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
b[i]=c[i]=0;
}
for(int i=1;i<=m;++i){
for(int j=0;j<n;++j){
scanf("%d",&a[j]);
if(a[j]==1){
b[i]|=(1<<j);
c[i]|=(1<<j);
}
if(a[j]==0){
c[i]|=(1<<j);
}
}
}
printf("%d\n",bfs());
}
int main(){
init();
return 0;
}