3.21~3.29 刷题记录
shadowice1984
2019-03-24 21:14:33
3.21
## T1
维护一个数列
支持
单点修改数列的一个位置
询问区间$(l,r)$在之前的所有时刻中区间和的历史最小值
一开始还想有没有什么高论，最后发现正解的做法和我一样丢人,都是$O(nlogn\sqrt{m})$的
我们可以假设数列一开始都是0，这样求出的历史最小值加上初始状态的区间和就是答案
然后我们还需要把修改变成加法，这些都好说
先考虑只有一个询问怎么做，将这个区间当中的修改拉出来按照时间排个序，我们发现可以使用一个二元组$(sum,min)$(修改的值之和，修改过程中区间和的最小值)来描述一段操作序列，不断合并即可出解
现在有一堆询问了，怎么办呢？
~~莫队啊~~
让我们来写个大暴力，使用以时间为下标的线段树我们可以粗暴的维护这个操作序列并且支持删除和插入，此时我们发现我们的询问就变成了一个区间查询
这样我们就做完了这道题啦~
~~备注，这份代码有很多的奇技淫巧~~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int B=6;const int B2=333;typedef long long ll;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
struct data
{
ll cur;ll mi;
friend data operator +(data a,data b)
{return (data){a.cur+b.cur,min(a.mi,a.cur+b.mi)};}
}a[N];int TOT;struct qry{int l;int r;int tim;int id;}qr[N];
int cntq;ll ans[N];ll ori[N];int cnt[N];int pos[N];
int A_bas[N<<1];int* A_t;int* ve[N];int tim;int n;int m;
ll sum[N];int bi[N];int bj[N];int pl[N];bool book[N];
struct linetree
{
data msk[N/B+3][(1<<B)+2];data v[4*N];int loc[N];int cur[N];
inline void build(int p,int l,int r)
{
if(r-l==1)
{
loc[r]=p;
for(int s=0;s<(1<<B);s++)
for(int i=0;i<B;i++)
if((s>>i)&1)msk[r][s]=msk[r][s]+a[i+pl[r]];return;
}int mid=(l+r)>>1;build(p<<1,l,mid);build(p<<1|1,mid,r);
}inline void modify(int pos)
{
TOT++;int r=bi[pos];int p=loc[r];book[pos]^=1;
cur[r]^=(1<<bj[pos]);v[p]=msk[r][cur[r]];
while(p!=1)p>>=1,v[p]=v[p<<1]+v[p<<1|1];
}inline data qry(int p,int l,int r,int dl,int dr)
{
if(dl==l&&dr==r)return v[p];int mid=(l+r)>>1;data ret=(data){0,0};
if(dl<mid)ret=ret+qry(p<<1,l,mid,dl,min(dr,mid));
if(mid<dr)ret=ret+qry(p<<1|1,mid,r,max(dl,mid),dr);return ret;
}inline data cqry(int nwt)
{
data ret=(data){0,0};
if(nwt<=B){for(int i=1;i<=nwt;i++)if(book[i])ret=ret+a[i];return ret;}
ret=qry(1,0,bi[tim],0,bi[nwt]-1);
for(int i=pl[bi[nwt]];i<=nwt;i++)if(book[i])ret=ret+a[i];
data bret=(data){0,0};
for(int i=1;i<=nwt;i++)if(book[i])bret=bret+a[i];
return ret;
}
}lt;
inline bool cmp1(const qry& a,const qry& b){return a.l<b.l;}
inline bool cmp2(const qry& a,const qry& b){return a.r<b.r;}
inline bool cmp3(const qry& a,const qry& b){return a.r>b.r;}
inline void chan(int lo){for(int i=0;i<cnt[lo];i++)lt.modify(ve[lo][i]);}
inline void pre()
{
for(int i=1;i<=tim;i++)bi[i]=((i-1)/B)+1;for(int i=1;i<=tim;i++)bj[i]=(i-1)%B;
for(int i=tim;i>=1;i--)pl[bi[i]]=i;for(int i=1;i<=tim;i++)cnt[pos[i]]++;
for(int i=1;i<=n;i++)gm(A_t,cnt[i],ve[i]),cnt[i]=0;
for(int i=1;i<=tim;i++)ve[pos[i]][cnt[pos[i]]++]=i;
if(bi[tim]!=0)lt.build(1,0,bi[tim]);
}
int main()
{
freopen("ds.in","r",stdin);freopen("ds.out","w",stdout);
scanf("%d%d",&n,&m);A_t=A_bas;
for(int i=1;i<=n;i++)scanf("%lld",&ori[i]);
for(int i=1;i<=n;i++)sum[i]=ori[i]+sum[i-1];
for(int i=1,tp,l,r;i<=m;i++)
{
scanf("%d%d%d",&tp,&l,&r);ll del;
if(tp==1)del=r-ori[l],ori[l]=r,a[++tim]=(data){del,min(0LL,del)},pos[tim]=l;
else ++cntq,qr[cntq]=(qry){l,r,tim,cntq};
}pre();sort(qr+1,qr+cntq+1,cmp1);
for(int l=1,id=1,r;l<=cntq;l+=B2,id++)
r=min(cntq+1,l+B2),sort(qr+l,qr+r,(id&1)?cmp2:cmp3);
int dl=0;int dr=-1;
for(int i=1;i<=cntq;i++)
{
if(dr<qr[i].l||dl>qr[i].r)
{
for(int j=dl;j<=dr;j++)chan(j);dl=qr[i].l;dr=qr[i].r;
for(int j=dl;j<=dr;j++)chan(j);
}else
{
while(dl<qr[i].l)chan(dl++);while(dl>qr[i].l)chan(--dl);
while(dr<qr[i].r)chan(++dr);while(dr>qr[i].r)chan(dr--);
}
ans[qr[i].id]=sum[dr]-sum[dl-1]+lt.cqry(qr[i].tim).mi;
}for(int i=1;i<=cntq;i++)printf("%lld\n",ans[i]);return 0;
}
```
## T2
一句话题意
求
$$\frac{1}{{n \choose k}}\sum_{d=1}^{n}A^{d}{n-d \choose k-1}$$
其中$n \leq 10^9,k \leq 10^7$
众所周知的是
$${n \choose k}=\frac{n^{\underline{k}}}{k!}$$
借助这个式子我们可以$O(k)$的计算组合数
所以我们的目标就是计算
$$\sum_{d=1}^{n}A^{d}{n-d \choose k-1}$$
稍微翻转一下下标我们会得到
$$\sum_{d=0}^{n-1}A^{n-d}{d \choose k-1}$$
我们令$B=A^{-1}$，并且令函数
$$g(n,k)=\sum_{d=0}^{n}B^{d}{d \choose k}$$
那么答案就是
$$A^{n}g(n-1,k-1)$$
所以现在我们考虑一下怎么计算函数$g$
答案是大力使用加法公式展开$g$函数
$$g(n,k)=\sum_{d=1}^{n}B^{d}{d-1 \choose k}+\sum_{d=1}^{n}B^{d}{d-1 \choose k-1}$$
让我们稍微凑一下式子
$$g(n,k)=B(\sum_{d=1}^{n}B^{d-1}{d-1 \choose k}+\sum_{d=1}^{n}B^{d-1}{d-1 \choose k-1})$$
将变量重新命名
$$g(n,k)=B(\sum_{d=0}^{n-1}B^{d}{d \choose k}+\sum_{d=0}^{n-1}B^{d}{d \choose k-1})$$
所以我们搞出来了这样的一个递推式
$$g(n,k)=B(g(n-1,k)+g(n-1,k-1))$$
边界条件是
$$g(n,0)=\sum_{d=0}^{n}B^d$$
是个等比数列求和
然后接下来才是真正sao的地方
我们注意到
$$g(n-1,k)=g(n,k)-B^n{n \choose k}$$
然后把这东西带入到原来的递推式当中
$$g(n,k)=Bg(n,k)-B^{n+1}{n \choose k}+Bg(n-1,k-1)$$
然后做一些初等的变换
$$g(n,k)=+\frac{B}{1-B}g(n-1,k-1)-\frac{B^{n+1}}{1-B}{n \choose k}$$
wow,我们得到了一个船新的递推式！
此时借助这个递推式$O(k)$的求解$g(n,k)$就行了，注意特判$A=1$的情况
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e7+10;typedef long long ll;const ll mod=998244353;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
ll ifac[N];ll inv[N];int n;int k;int a;
inline void pre()
{
inv[0]=inv[1]=1;for(int i=2;i<N;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ifac[0]=1;for(int i=1;i<N;i++)ifac[i]=ifac[i-1]*inv[i]%mod;
}
inline void solve()
{
scanf("%d%d%d",&n,&k,&a);
if(n==1){printf("%d\n",a);return;}
if(a==1){printf("1\n");return;}
ll b=po(a,mod-2);ll q=b*po((1+mod-b)%mod,mod-2)%mod;
n--;k--;int tn=n-k;ll cc=1;ll pb=po(b,tn+1)*po((1+mod-b)%mod,mod-2)%mod;
ll cf=(po(b,tn+1)+mod-1)*po((b+mod-1)%mod,mod-2)%mod;
for(int i=1;i<=k;i++)
{
tn++;(cc*=tn*inv[i]%mod)%=mod;(pb*=b)%=mod;
cf=(cf*q+(mod-pb)*cc)%mod;
}k++;n++;cf=cf*po(a,n)%mod;
cc=cc*n%mod*inv[k]%mod;printf("%lld\n",cf*po(cc,mod-2)%mod);
}
int main()
{freopen("set.in","r",stdin);freopen("set.out","w",stdout);
pre();int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;}
```
3.24
## T1
给定一个$2×n$的地图，地图当中有障碍和箱子和空位，在$(0,0)$和$(0,n-1)$处有两个人$A,B$
你现在可以做如下操作
让一个箱子移动一格或者让一个人移动一格，如果箱子或人在第一排则不能让箱子或者人横向移动
问能不能将$A,B$交换位置
观察到如果存在两个时刻$x1,x2$使得$A,B$交换了位置而其他箱子的位置不动，就证明有解
具体来讲我们只要将$(0,x1)$中的操作倒着作用于$x2$时刻的状态就行了
手玩一下各种情况发现只要$A$到了$B$的右侧就会出现时刻$x1,x2$
所以现在的问题只是$A$能不能到$B$的位置上去
那贪心就好了，我们每次贪心的把人尽可能的向$B$的左边移，模拟即可
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=2*1e3+10;typedef long long ll;
int ctt;int tr[2][N];int n;
struct bcj
{
int fa[N*2];
inline void ih(){for(int i=1;i<=2*n;i++)fa[i]=i;}
inline int f(int x){return fa[x]=(fa[x]==x)?x:f(fa[x]);}
inline void u(int x,int y){fa[f(x)]=f(y);}
}s;char mde[2][N];int sum[N];int tot;
inline void solve()
{
scanf("%s",mde[0]+1);scanf("%s",mde[1]+1);
n=1;while(mde[0][n+1]!='\0')n++;s.ih();
for(int i=2;i<=n;i++)
if(mde[1][i]!='#'&&mde[1][i-1]!='#')s.u(tr[1][i],tr[1][i-1]);
for(int i=1;i<=n;i++)
if(mde[0][i]!='#'&&mde[1][i]!='#')s.u(tr[0][i],tr[1][i]);
if(s.f(tr[0][1])!=s.f(tr[0][n])){printf("Impossible\n");return;}
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+(mde[0][i]!='#')+(mde[1][i]!='#');
// for(int i=1;i<=n;i++)printf("%d ",sum[i]);printf("\n");
tot=0;
for(int i=1;i<=n;i++)tot+=(mde[0][i]!='#')&&(mde[0][i]!='.');
for(int i=1;i<=n;i++)tot+=(mde[1][i]!='#')&&(mde[1][i]!='.');
if(sum[n]==tot){printf("Impossible\n");return;}
tot--;int pos=n;int rem=0;
while(tot)
{
if(mde[0][pos]!='#')
{
int del=sum[n]-sum[pos]-rem;
del=min(del,tot);rem+=del;tot-=del;
}
if(sum[pos-2]<tot){printf("Impossible\n");return;}
pos--;
}printf("Possible\n");return;
}
int main()
{
// freopen("tst.txt","r",stdin);//freopen("run.txt","w",stdout);
freopen("swap.in","r",stdin);freopen("swap.out","w",stdout);
for(int i=1;i<N;i++)tr[0][i]=++ctt,tr[1][i]=++ctt;
int T;scanf("%d",&T);for(int z=1;z<=T;z++)solve();return 0;
}
```
## T3
在二维平面上给出两个点的集合$W,S$现在要求你画一些底边贴着$x$轴的矩形，使得点集$W$中的点都在你画出的矩形当中而$S$中的点都不在你画出的矩形中，保证有解
这题有两问
1.求解最少需要几个矩形
2.将$W$的所有子集都作为输入求一遍问题1，(注意此时$S$是不变的)
求这些问题1的答案之和
将所有坐标按照$x$排序，那么对于$W$中相邻的两个点我们可以求出这两个点之间的$S$点y坐标的最小值，我们可以把这东西看成$height$一样的东西，因为如果想画一个矩形覆盖$l,r$这段区间，那么这个矩形的高度不得超过height的区间最小值
那么我们可以对$height$建笛卡尔树，此时我们发现可以使用贪心解决问题1，每个点维护一个当前子树中未被覆盖点的y坐标的最大值，那么只要父亲不能覆盖这个点了我们就不能接着鸽下去了，此时会让答案$+1$
对于问题2，先把问题1的代码写出来，然后把问题1当中的变量变成一个数组，数组的第i位表示有多少种方案使得这个变量的取值是$i$，考虑每个变量对答案的贡献即可
```C
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=4*1e3+10;typedef long long ll;const ll mod=1e9+7;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
struct data
{
int pos;int val;
friend bool operator <(data a,data b){return a.pos<b.pos;}
}a[N];map<int,int> mp;
int hw[N];int ht[N];int hd;int typ;int w;int s;
inline void pre()
{
scanf("%d%d%d",&typ,&w,&s);
for(int i=1;i<=w;i++)scanf("%d%d",&a[i].pos,&a[i].val);
for(int i=1,x,y;i<=s;i++)
{scanf("%d%d",&x,&y);if(!mp.count(x))mp[x]=y;else mp[x]=min(mp[x],y);}
sort(a+1,a+w+1);
for(int i=1;i<=w;i++)
{
hw[++hd]=a[i].val;ht[hd]=0x3f3f3f3f;
if(i==w)break;
map <int,int> :: iterator it=mp.lower_bound(a[i].pos);
for(;it!=mp.end()&&it->first<=a[i+1].pos;++it)
ht[hd]=min(ht[hd],it->second);
}
}
namespace solver1
{
int ans=0;
inline int solve(int l,int r,int fa)
{
if(l==r)return (hw[l]>=fa)?(ans++,-1):hw[l];
int mid=-1;int miv=0x3f3f3f3f+3;
for(int i=l;i<r;i++)if(miv>ht[i])miv=ht[i],mid=i;
int mx=max(solve(l,mid,miv),solve(mid+1,r,miv));
return (mx>=fa)?(ans++,-1):mx;
}inline void mainsolve(){solve(1,hd,0);printf("%d",ans);return;}
}
namespace solver2
{
struct data{int pos;ll val;}D_bas[N*N];data* D_t;ll mi[N<<2];ll ans=0;
struct var
{
data* ve;int hd;
inline data& operator [](const int& x){return ve[x];}
friend var operator +(var a,var b)
{
map <int,ll> mp;
for(int i=0;i<a.hd;i++)
for(int j=0;j<b.hd;j++)
(mp[max(a[i].pos,b[j].pos)]+=a[i].val*b[j].val)%=mod;
var c;gm(D_t,mp.size(),c.ve);c.hd=0;
for(map <int,ll>:: iterator it=mp.begin();it!=mp.end();++it)
c[c.hd++]=(data){it->first,it->second};return c;
}var pop(ll& ans,int lim,ll tmp)
{
var c;c.ve=D_t;c.hd=0;
c[c.hd++]=ve[0];ll& rem=c[0].val;
for(int i=1;i<hd;i++)
{
if(ve[i].pos>=lim)(ans+=ve[i].val*tmp)%=mod,(rem+=ve[i].val)%=mod;
else c[c.hd++]=ve[i];
}D_t+=c.hd;return c;
}
};inline var solve(int l,int r,int fa)
{
var mx;if(l==r)
{
mx.ve=D_t;mx.hd=0;mx[mx.hd++]=(data){-1,1};
mx[mx.hd++]=(data){hw[l],1};D_t+=2;goto ed;
}{
int mid=-1;int miv=0x3f3f3f3f+3;
for(int i=l;i<r;i++)
if(miv>ht[i])miv=ht[i],mid=i;
mx=solve(l,mid,miv)+solve(mid+1,r,miv);
}
ed:return mx.pop(ans,fa,mi[w-(r-l+1)]);
}inline void mainsolve()
{
D_t=D_bas;mi[0]=1;
for(int i=1;i<(N<<2);i++)mi[i]=mi[i-1]*2%mod;solve(1,hd,0);
printf("%lld\n",ans);
}
}
int main()
{
freopen("cover.in","r",stdin);freopen("cover.out","w",stdout);
pre();if(typ==0)solver1::mainsolve();else solver2::mainsolve();return 0;
}
```
## 3.25
啊为啥我总是不会$T2$啊
## T1
给出一张$DAG$每次给定一个点集$S$，询问这个点集的导出子图有多少条路径
额思博题啊，由于点集的siz之和不是很大因此我们给边重新定向，让小度点指向大度点，重定向之后每个点的出度将小于$\sqrt{M}$这样我们建图的复杂度就真了
复杂度$O(\sqrt{M}\sum|S|)$
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int E=2*1e5+10;
typedef unsigned long long ll;const ll mod=1e9+7;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
# define md(x) (x=(x>=mod)?x-mod:x)
namespace SMG
{
int v[E];int x[E];int al[N];int ct;ll dp[N];bool book[N];
inline void add(int u,int V){if(u>V)swap(u,V);v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline ll dfs(int u)
{
if(book[u])return dp[u];book[u]=true;dp[u]=1;
for(int i=al[u];i;i=x[i])dp[u]+=dfs(v[i]),md(dp[u]);
return dp[u];
}inline ll solve(int* qu,int hd)
{
for(int i=1;i<=hd;i++)book[qu[i]]=false;
for(int i=1;i<=hd;i++)if(!book[qu[i]])dfs(qu[i]);
ll ret=0;for(int i=1;i<=hd;i++)ret+=dp[qu[i]],md(ret);
for(int i=1;i<=hd;i++)al[qu[i]]=0;ct=0;
return (ret+mod-hd)%mod;
}
}
struct ed{int u;int v;}eg[E];int dg[N];bool book[N];int qu[N];int hd;
int A_bas[E<<2];int* A_t;int* ve[N];int nd[N];int n;int m;
inline void solve(int* qu,int hd)
{
for(int i=1;i<=hd;i++)book[qu[i]]=true;
for(int i=1;i<=hd;i++)
for(int* v=ve[qu[i]];v!=ve[qu[i]]+nd[qu[i]];++v)
if(book[*v])SMG::add(qu[i],*v);
printf("%lld\n",SMG::solve(qu,hd));
for(int i=1;i<=hd;i++)book[qu[i]]=false;
}
int main()
{
//freopen("gondola_sample.in","r",stdin);
freopen("gondola.in","r",stdin);freopen("gondola.out","w",stdout);
A_t=A_bas;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&eg[i].u,&eg[i].v),dg[eg[i].u]++,dg[eg[i].v]++;
for(int i=1;i<=m;i++)
{
int& u=eg[i].u;int& v=eg[i].v;
if(dg[u]>dg[v])swap(u,v);nd[u]++;
}
for(int i=1;i<=n;i++)gm(A_t,nd[i],ve[i]),nd[i]=0;
for(int i=1;i<=m;i++)ve[eg[i].u][nd[eg[i].u]++]=eg[i].v;
int q;scanf("%d",&q);
for(int i=1;i<=q;i++)
{scanf("%d",&hd);for(int j=1;j<=hd;j++)scanf("%d",&qu[j]);solve(qu,hd);}
return 0;
}
```
## T3
给定一颗树初始所有边都是白的，支持
1.将$u,v$路径上的边全部取反，也就是黑色变成白色白色变成黑色
2.如果仅仅保留树上的所有白边，求出点x所在联通块的大小
额啥也没想就写了个3个$log$的大暴力上去，没想到踩标算了……
其实思路很trival，就是无脑树剖那一套
每个点维护一个值lightson表示仅仅考虑轻孩子的时候这个点所在的联通块大小
那么我们考虑怎么算一个点所在的联通块大小
其实很简单，如果这个点和重链顶的父亲不连通的话，我们可以在重链上找到这个点可以到达的最深的和最浅的点，然后查一发lightson的区间和就可以出解了
如果联通的话说明此时的答案和重链顶的父亲是一样的，递归去找就行了
现在考虑怎么维护lightson的值，那么每个重链顶额外维护一个值$hsiz$表示不考虑父亲边时这个点所在联通块的size
那显然一个点的lightson值就是它的所有和他相连的轻儿子的hsiz之和再加1
现在来考虑修改怎么修改，我们将修改拆成$O(logn)$个重链取反和轻边取反
先来考虑重链取反会产生什么影响,我们每个重链开一个线段树来维护那些边是黑的那些边是白的，这样我们就能在线段树上二分找到重链顶能到达的最低点是谁，此时重链顶的hsiz会发生变化，然后会导致父亲的lightsiz发生变化……如此反复下去一路更新即可，单次复杂度是$O(log^2n)$的
现在来考虑轻边取反也是类似的会导致一个点的lightsize变化，然后导致链顶的hsiz变化，还是反复跳轻边更新即可，单次复杂度还是$O(log^2n)$的
查询的时候需要找最上面和这个点联通的点以及最下面和这个点联通的点，依然在线段树上二分就好了
然后这东西跑了100ms……
因为这三个log中的两个log是树剖的log另一个是树状数组的log，常数自己感受一下，顺便说一句我每个重链单开的树状数组
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;typedef long long ll;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
int A_bas[N<<5];int* A_t;struct data{int p;int l;int r;}qu[N];int hd;
struct linetree
{
int* v;int* rv;int RG;
inline void cons(int siz){RG=siz;gm(A_t,RG<<2,v);gm(A_t,RG<<2,rv);}
inline void pd(int p,int l1,int l2)
{
if(rv[p])
{
rv[p<<1|1]^=1;v[p<<1|1]=l2-v[p<<1|1];
rv[p<<1]^=1;v[p<<1]=l1-v[p<<1];rv[p]=0;
}
}inline void strv(int p,int l,int r,int dl,int dr)
{
if(dl==l&&dr==r){rv[p]^=1;v[p]=(r-l)-v[p];return;}
int mid=(l+r)>>1;pd(p,mid-l,r-mid);
if(dl<mid)strv(p<<1,l,mid,dl,min(dr,mid));
if(mid<dr)strv(p<<1|1,mid,r,max(dl,mid),dr);v[p]=v[p<<1]+v[p<<1|1];
}inline void extr(int p,int l,int r,int dl,int dr)
{
if(dl==l&&dr==r){qu[++hd]=(data){p,l,r};return;}int mid=(l+r)>>1;pd(p,mid-l,r-mid);
if(dl<mid)extr(p<<1,l,mid,dl,min(dr,mid));
if(mid<dr)extr(p<<1|1,mid,r,max(dl,mid),dr);
}inline int cpre(int p,int l,int r)
{
if(r-l==1)return r;int mid=(l+r)>>1;pd(p,mid-l,r-mid);
return (v[p<<1])?cpre(p<<1,l,mid):cpre(p<<1|1,mid,r);
}inline int csuf(int p,int l,int r)
{
if(r-l==1)return r;int mid=(l+r)>>1;pd(p,mid-l,r-mid);
return (v[p<<1|1])?csuf(p<<1|1,mid,r):csuf(p<<1,l,mid);
}inline int pre(int pos)
{
if(pos<=0)return -1;hd=0;extr(1,0,RG,0,pos);
for(int i=hd;i>=1;i--)if(v[qu[i].p])return csuf(qu[i].p,qu[i].l,qu[i].r);
return -1;
}inline int suf(int pos)
{
if(pos>RG)return 0x3f3f3f3f;hd=0;extr(1,0,RG,pos-1,RG);
for(int i=1;i<=hd;i++)if(v[qu[i].p])return cpre(qu[i].p,qu[i].l,qu[i].r);
return 0x3f3f3f3f;
}
};
struct solver
{
int* ta;int siz;linetree lt;int mip;
inline void cons(int RG){siz=RG;lt.cons(siz-1);mip=siz;gm(A_t,siz+1,ta);}
inline void c(int x,int t){for(;x<=siz;x+=x&(-x))ta[x]+=t;}
inline int q(int x){int r=0;for(;x;x-=x&(-x))r+=ta[x];return r;}
inline void reverse(int l,int r)
{if(l==r)return;lt.strv(1,0,siz-1,l-1,r-1);mip=min(lt.suf(1),siz);}
inline int ghsiz(){return q(mip);}
inline int qsiz(int pos)
{
int l=max(lt.pre(pos-1)+1,1);int r=min(siz,lt.suf(pos));
return q(r)-q(l-1);
}
}sl[N];
int v[N<<1];int x[N<<1];int ct;int al[N];int dep[N];int av[N];
int h[N];int siz[N];int st[N];int tp;int nu[N];int top[N];int fa[N];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline int dfs1(int u)
{
for(int i=al[u];i;i=x[i])
if(v[i]!=fa[u])fa[v[i]]=u,dep[v[i]]=dep[u]+1,
siz[u]+=dfs1(v[i]),h[u]=(siz[h[u]]<siz[v[i]])?v[i]:h[u];
return ++siz[u];
}inline void solve(int u)
{
for(int p=u,lst=fa[u];p;lst=p,p=h[p])
for(int i=al[p];i;i=x[i])if(v[i]!=lst&&v[i]!=h[p])solve(v[i]);
tp=0;for(int p=u;p;p=h[p])st[++tp]=p;
for(int i=1;i<=tp;i++)nu[st[i]]=i;
for(int i=1;i<=tp;i++)top[st[i]]=u;sl[u].cons(tp);
for(int i=1;i<=tp;i++)sl[u].c(i,siz[st[i]]-siz[h[st[i]]]);
}
inline void sfix(int u,int old)
{
if(u==1||av[u])return;
int nxt=top[fa[u]];int nold=sl[nxt].ghsiz();
sl[nxt].c(nu[fa[u]],sl[u].ghsiz()-old);sfix(nxt,nold);
}
inline void heavy_reverse(int u,int l,int r)
{int old=sl[u].ghsiz();sl[u].reverse(l,r);sfix(u,old);}
inline void light_reverse(int u)
{
if(u==1)return;
int del=sl[u].ghsiz();del=(av[u])?del:-del;av[u]^=1;
int nxt=top[fa[u]];int old=sl[nxt].ghsiz();
sl[nxt].c(nu[fa[u]],del);sfix(nxt,old);
}inline void modify(int u,int v)
{
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]])swap(u,v);
heavy_reverse(top[u],nu[top[u]],nu[u]);
light_reverse(top[u]);u=fa[top[u]];
}if(dep[u]>dep[v])swap(u,v);heavy_reverse(top[u],nu[u],nu[v]);
}inline int gsiz(int u)
{
int txp=top[u];
if(txp==1||av[txp]||nu[u]>sl[txp].mip)return sl[txp].qsiz(nu[u]);
else return gsiz(fa[txp]);
}
int main()
{
freopen("scary.in","r",stdin);freopen("scary.out","w",stdout);
A_t=A_bas;int n;int m;scanf("%d%d",&n,&m);
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs1(1);solve(1);for(int i=1,tp,u,v;i<=m;i++)
{
scanf("%d",&tp);
if(tp==1)scanf("%d%d",&u,&v),modify(u,v);
else scanf("%d",&u),printf("%d\n",gsiz(u));
}return 0;
}
```
## 3.26
## T1
给你一棵树，问有多少个点的集合大小恰好为k并且最远点对间的距离不超过len，多组询问
据说有组合数的优秀$O(n^2)$，然而这只shadowice太菜并不会
通道里有个结论，如果树的边权都是正的那么点集$A \cup B$的最远点对一定在$A$的最远点对和$B$的最远点对之间产生
所以可以直接大力$dp(i,u,v,t)$表示这个点集属于i的子树最远点对为u和v大小为t的方案数
虽然状态数是$O(n^4)$的不过状态并不会卡满于是就过去了
```C
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=1e2+10;const int M=1e7+10;
typedef long long ll;const ll mod=1e9+7;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
int n;int m;int v[N<<1];int x[N<<1];int ct;int val[N<<1];int al[N];ll dis[N][N];
inline void add(int u,int V,ll va){v[++ct]=V;x[ct]=al[u];al[u]=ct;val[ct]=va;}
inline void ckmx(int& ru,int& rv,int tu,int tv){if(dis[ru][rv]<dis[tu][tv])ru=tu,rv=tv;}
struct data
{
int p1;int p2;int t;ll v;
friend data operator +(data a,data b)
{
data c=a;c.v=a.v*b.v%mod;
ckmx(c.p1,c.p2,b.p1,b.p2);ckmx(c.p1,c.p2,a.p1,b.p1);
ckmx(c.p1,c.p2,a.p1,b.p2);ckmx(c.p1,c.p2,a.p2,b.p1);
ckmx(c.p1,c.p2,a.p2,b.p2);c.t+=b.t;
if(c.p1>c.p2)swap(c.p1,c.p2);return c;
}
}D_bas[M];data* dp[N];int hd[N];data* D_t;
int A_bas[N*N*4];int* qu[N];int siz[N];int* A_t;
int trq[N];data trd[N*N*N];ll tval[N][N][N];
inline void dfs(int u,int f,ll* dis)
{
for(int i=al[u];i;i=x[i])
if(v[i]!=f)dis[v[i]]=dis[u]+val[i],dfs(v[i],u,dis);
}
# define md(x) (x=(x>=mod)?x-mod:x)
inline void dfs1(int u,int f)
{
for(int z=al[u];z;z=x[z])if(v[z]!=f)dfs1(v[z],u);
int hdp=1;int tsiz=1;trd[1]=(data){u,u,1,1};trq[1]=u;
for(int z=al[u];z;z=x[z])
{
int tw=v[z];if(tw==f)continue;
for(int i=1;i<=hdp;i++)
{ll& va=tval[trd[i].p1][trd[i].p2][trd[i].t];va+=trd[i].v,md(va);}
data* p=dp[tw];for(int i=1;i<=hd[tw];i++)
{ll& va=tval[p[i].p1][p[i].p2][p[i].t];va+=p[i].v,md(va);}
for(int i=1;i<=hdp;i++)
for(int j=1;j<=hd[tw];j++)
{data c=trd[i]+p[j];ll& va=tval[c.p1][c.p2][c.t];va+=c.v;md(va);}
// printf("mg %d %d\n",u,tw);
// for(int i=1;i<=tsiz;i++)printf("%d ",trq[i]);printf("\n");
for(int i=1;i<=siz[tw];i++)trq[++tsiz]=qu[tw][i];
sort(trq+1,trq+tsiz+1);
// printf("dp %d %d\n",u,tw);
// for(int i=1;i<=tsiz;i++)printf("%d ",trq[i]);printf("\n");
hdp=0;
for(int p1=1;p1<=tsiz;p1++)
for(int p2=p1;p2<=tsiz;p2++)
for(int t=1;t<=tsiz;t++)
{
ll& va=tval[trq[p1]][trq[p2]][t];
if(va!=0)trd[++hdp]=(data){trq[p1],trq[p2],t,va},va=0;
}
}gm(D_t,hdp+1,dp[u]);gm(A_t,tsiz+1,qu[u]);
// printf("hdp=%d,tsiz=%d\n",hdp,tsiz);
for(int i=1;i<=hdp;i++)dp[u][i]=trd[i];hd[u]=hdp;
for(int i=1;i<=tsiz;i++)qu[u][i]=trq[i];siz[u]=tsiz;
// printf("fin %d\n",u);
// for(int i=1;i<=siz[u];i++)
// printf("%d ",qu[u][i]);printf("\n");
}
map <ll,ll> ans[N];
int main()
{
//system("fc catering_sample.out tst.txt");return 0;
// freopen("catering_sample.in","r",stdin);//freopen("tst.txt","w",stdout);
freopen("catering.in","r",stdin);freopen("catering.out","w",stdout);
// freopen("tst.txt","r",stdin);
scanf("%d%d",&n,&m);D_t=D_bas;A_t=A_bas;
for(int i=1,u,v,va;i<n;i++)scanf("%d%d%d",&u,&v,&va),add(u,v,va),add(v,u,va);
for(int i=1;i<=n;i++)dfs(i,0,dis[i]);dfs1(1,0);
// for(Mdi it=dp[1].begin();it!=dp[1].end();++it)
// (ans[it->first.t][dis[it->first.p1][it->first.p2]]+=it->second)%=mod;
for(int i=1;i<=hd[1];i++)
(ans[dp[1][i].t][dis[dp[1][i].p1][dp[1][i].p2]]+=dp[1][i].v)%=mod;
for(int i=1;i<=n;i++)
{
map <ll,ll> :: iterator it1,it2;
if(ans[i].empty())continue;
for(it1=ans[i].begin(),it2=it1,++it2;it2!=ans[i].end();++it1,++it2)
(it2->second+=it1->second)%=mod;
}
// return 0;
for(int i=1;i<=m;i++)
{
int k;ll len;scanf("%d%lld",&k,&len);
map <ll,ll> :: iterator it=ans[k].upper_bound(len);
// printf("%lld ,%lld\n",it->second,it->first);
if(it==ans[k].begin())printf("0\n");
else --it,printf("%lld\n",it->second);
}return 0;
}
```
## T2
你需要雇佣印度女工来帮你干活，每个人每天可以完成一件任务，每个任务有一个deadline，现在给你一个序列，求为了在每件任务的deadline之前完成他们至少需要几名印度女工
支持动态的插入k个dealine相同的任务
假设有p个女工不停的干活那么每天可以完成p件任务，那么将任务按照ddl排序之后如果一个任务的排名是rk，那么这个任务的完成时间就是$\lceil \frac{rk}{p} \rceil$,然后随手折腾折腾式子会发现答案就是
$$\max_{i}(\lceil \frac{rk_{i}}{lim_{i}} \rceil)$$
显然多个任务ddl相同的时候只需保留排名最大的那个
设时间i截止的任务有$s_{i}$个，对这个数组做前缀和之后是$sum_{i}$,那么答案就是
$$max_{i}(\lceil \frac{sum_{i}}{i} \rceil) $$
现在需要支持对$sum$数组进行区间加法
那么分块套个凸包维护一下就行了
不知道为什么double的精度很高于是并不会被掐精度
上代码~
```C
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=1e5+10;const int RG=1e5;const int B=320;typedef long double db;
namespace INPUT_SPACE{
// const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
//char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
char gc(){return getchar();}
inline int inn()
{
int x,ch,sgn=1;while(((ch=gc())<'0'||ch>'9')&&ch!='-');
if(ch=='-') sgn=-1,x=0;else x=ch^'0';
while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
return x*sgn;
}
}using INPUT_SPACE::inn;
struct data
{
double x;double y;int rx;
friend data operator +(data a,data b){return (data){a.x+b.x,a.y+b.y,0};}
friend data operator -(data a,data b){
//printf("k=%.13lf\n",(a.x-b.x)/(a.y-b.y));
return (data){a.x-b.x,a.y-b.y,0};}
friend bool operator <(data a,data b){
//printf("key1=%.13lf,key2=%.13lf\n",a.x*b.y,b.x*a.y);
//printf("k1=%.13lf,k2=%.13lf\n",a.x/a.y)
return a.y*b.x<b.y*a.x;}
}a[N];
inline bool cmp(const data& a,const data& b){return a.rx>b.rx;}
inline bool cmp1(const data& a,const data& b){return a.rx<b.rx;}
inline void calchull(data* st,int& tp)
{
if(tp<=2)return;int lim;int i;
for(lim=tp,i=3,tp=2;i<=lim;i++)
{
while(tp>=2&&(st[tp]-st[tp-1])<(st[i]-st[tp-1]))tp--;
st[++tp]=st[i];
// for(int j=1;j<=tp;j++)printf("<%.3lf,%.3lf>,",st[j].x,st[j].y);printf("\n");
}
}int bi[N];int bj[N];
struct blk
{
data hull[B+3];int px[B+3];int py[B+3];int tp;int cur;
int lb=0;db bst;int siz;int ans;
inline int& operator [](const int& x){return py[x];}
inline void rebuild()
{
for(int i=1;i<=siz;i++)hull[siz-i+1]=(data){1.0/px[i],(double)py[i]/px[i],i};
// for(int i=1;i<=siz;i++)printf("%d ",py[i]);printf("\n");
// for(int i=1;i<=siz;i++)printf("<%.3lf>,",hull[i].x);printf("\n");
tp=siz;calchull(hull,tp);
// for(int i=1;i<=tp;i++)printf("<%.3lf>,",hull[i].x);printf("\n");
cur=1;bst=(double)hull[1].y;
while(cur!=tp&&bst<(double)hull[cur+1].y)cur++,bst=hull[cur].y;
int id=hull[cur].rx;ans=(py[id]+px[id]-1)/px[id];
// printf("px(%d)=%d,py(%d)=%d\n",id,px[id],id,py[id]);
}
inline void lb_add(int x)
{
lb+=x;bst=hull[cur].y+lb*hull[cur].x;
while(cur!=tp&&bst<hull[cur+1].y+lb*hull[cur+1].x)
cur++,bst=hull[cur].y+lb*hull[cur].x;
int id=hull[cur].rx;ans=(py[id]+lb+px[id]-1)/px[id];
}
inline void rb_add(int pos,int x)
{
for(int i=pos;i<=siz;i++)py[i]+=x;
for(int i=1;i<=siz;i++)py[i]+=lb;lb=0;rebuild();
}
}bl[N/B+3];int n;int m;int q;int sum[N];
int main()
{
// freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
freopen("computer.in","r",stdin);freopen("computer.out","w",stdout);
//scanf("%d%d%d",&n,&m,&q);
n=inn();m=inn();q=inn();
for(int i=1;i<=n;i++)bi[i]=(i-1)/B+1;for(int i=1;i<=n;i++)bj[i]=(i-1)%B+1;
for(int i=1;i<=n;i++)bl[bi[i]].px[bj[i]]=i;
for(int i=1;i<bi[n];i++)bl[i].siz=B;bl[bi[n]].siz=(n%B)?n%B:B;
for(int i=1,x;i<=m;i++)//scanf("%d",&x)
x=inn()
,sum[x]++;
for(int i=1;i<=n;i++)sum[i]+=sum[i-1];
for(int i=1;i<=n;i++)bl[bi[i]][bj[i]]=sum[i];
for(int i=1;i<=bi[n];i++)bl[i].rebuild();
int ans=0;for(int i=1;i<=bi[n];i++)ans=max(ans,bl[i].ans);
printf("%d\n",ans);
for(int i=1,pos,val;i<=q;i++)
{
//scanf("%d%d",&val,&pos);
val=inn();pos=inn();
bl[bi[pos]].rb_add(bj[pos],val);
for(int i=bi[pos]+1;i<=bi[n];i++)bl[i].lb_add(val);
int ans=0;for(int i=1;i<=bi[n];i++)ans=max(ans,bl[i].ans);
printf("%d\n",ans);
}return 0;
}
```
## T3
给你一个网格状的dag(每个点只能向上或者向右走但是向上或者向右的路可能不通)，每个点有颜色，对于每个点输出，从这个点出发能到达的点集当中有几种颜色
正解很好写但是很神仙
我们优先向上走可以得到一个dfs序(这里使用后序遍历)，优先向右走可以得到另一个后序遍历，如果我们把$(dfn1,dfn2)$看成二维平面上的点，那么每个点能到达的点就是一个矩形
现在就是一个矩形数颜色的问题了，那我们数最靠上的就行了，扫描线套个树状数组即可
```C
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=3*1e5+10;typedef long long ll;
int dfn[N];int up[N];int rt[N];int x[N];int y[N];int val[N];
map <int,int> mf;int df;int n;int m;int ans[N];bool book[N];
struct treearray
{
int ta[N];
inline void c(int x,int t){for(;x<=n;x+=x&(-x))ta[x]+=t;}
inline int q(int x){int r=0;for(;x;x-=x&(-x))r+=ta[x];return r;}
}ta;
inline void dfs(int u)
{
book[u]=true;if(!book[up[u]])dfs(up[u]);
if(!book[rt[u]])dfs(rt[u]);dfn[u]=++df;
}
inline void dfs1(int u)
{
book[u]=true;
if(!book[rt[u]])dfs1(rt[u]);if(!book[up[u]])dfs1(up[u]);
if(mf.count(val[u]))
{int& nw=mf[val[u]];if(nw>dfn[u])ta.c(nw,-1),ta.c(nw=dfn[u],1);}
else mf[val[u]]=dfn[u],ta.c(dfn[u],1);ans[u]=ta.q(dfn[u]);
}
int main()
{
freopen("souvenir.in","r",stdin);freopen("souvenir.out","w",stdout);
scanf("%d%d",&n,&m);book[0]=true;
for(int i=1;i<=n;i++)scanf("%d%d%d",&x[i],&y[i],&val[i]);
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
if(x[u]==x[v]){if(y[u]>y[v])swap(u,v);rt[u]=v;}
else {if(x[u]>x[v])swap(u,v);up[u]=v;}
}dfs(1);
// for(int i=1;i<=n;i++)printf("%d ",dfn[i]);printf("\n");
for(int i=1;i<=n;i++)book[i]=false;
dfs1(1);for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}
```
## 3.27
## T1
给定一个正整数集合$S$定义$f(S)$表示符合以下条件的长度为$k$的向量的个数
> 向量当中的每个元素都在$S$当中
> 向量当中的所有元素之和是$n$的倍数
现在令全集$U$为小于$n$的所有非负整数,求
$$\sum_{T \subseteq U}f(T)$$
保证k一定是奇数
有个神仙结论,$k$是奇数的时候模$n$为1,2,3,4,5…的向量个数其实是一样多的
那么答案就是
$$\frac{1}{n}\sum_{i=1}^{n}{n \choose i}i^K$$
这个随便搞搞就行啦~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e2+10;typedef long long ll;const ll mod=998244353;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
inline ll dpo(ll a,ll p){ll r=1;for(int i=0;i<p;i++)(r*=a+mod-i)%=mod;return r;}
ll st[N][N];int n;int k;
int main()
{
freopen("songfenti.in","r",stdin);freopen("songfenti.out","w",stdout);
st[0][0]=1;
for(int i=1;i<N;i++)
for(int j=1;j<N;j++)
st[i][j]=(st[i-1][j-1]+st[i-1][j]*j)%mod;
scanf("%d%d",&n,&k);ll res=0;
for(int i=0;i<=min(n,k);i++)
(res+=st[k][i]*dpo(n,i)%mod*po(2,n-i))%=mod;
printf("%lld\n",res*po(n,mod-2)%mod);return 0;
}
```
## T2
给定一个可重的正整数集合$S$，你现在可以执行$k$次操作，操作为将集合$S$中的一个数字$x$变成$\lfloor \frac{x}{2} \rfloor$，问如何操作才能使得最后剩下的数字之和尽可能的少
现在把这个问题丢到树上,每次给出一个点$u$和一个值$k$询问你如果把$u$子树当中的数字作为刚才的$S$,那么答案是多少
卡空间:空间限制$64mb$
容易看出连续操作一个数字产生的收益递减，于是可以把一个数字反复操作$log$次，将每次的代价作为这个数字的权值，这样的话我们只需要贪心的取前k大即可产生一个合法并且最优的方案
直接上主席树是两个log的空间复杂度吃不消
我们考虑对值域分块，将$(2^k,2^k-1)$作为一块，这样每个块的权值大值是均等的，此时空间复杂度成了一个log，可以通过此题了
```C
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;const int N=1e5+10;typedef long long ll;int RG=(1<<30);
ll read()
{
ll v = 0, f = 1;
char c = getchar();
while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
return v * f;
}
int n;int m;int S;
struct linetree
{
int s[N*22][2];int v[N*22];ll sum[N*22];int ct;
//inline int ck(int& lk){return lk=(lk?lk:++ct);}
inline void ins(int p1,int p2,int l,int r,int pos,int cnt,ll va)
{
// printf("ins %d %d %d %d %d %d %lld\n",p1,p2,l,r,pos,cnt,va);
while(v[p2]=v[p1]+cnt,sum[p2]=sum[p1]+va,r-l!=1)
{
int mid=(l+r)>>1;
if(pos<=mid)r=mid,s[p2][1]=s[p1][1],p2=s[p2][0]=++ct,p1=s[p1][0];
else l=mid,s[p2][0]=s[p1][0],p2=s[p2][1]=++ct,p1=s[p1][1];
}//printf("v[%d,%d]=%lld,sum[%d,%d]=%lld\n",l,r,v[p2],l,r,sum[p2]);
}
inline void cpy(int p1,int p2)
{v[p2]=v[p1];sum[p2]=sum[p1];s[p2][0]=s[p1][0];s[p2][1]=s[p1][1];}
inline ll ksum(int p1,int p2,int l,int r,int& k)
{
if(v[p2]==v[p1])return 0;
// printf("ksum v[%d %d]=%d,sum[%d,%d]=%lld\n",l,r,v[p2]-v[p1],l,r,sum[p2]-sum[p1]);
if(r-l==1)
{
ll del=min(k,v[p2]-v[p1]);k-=del;
return del*((sum[p2]-sum[p1])/(v[p2]-v[p1]));
}int mid=(l+r)>>1;int v0=v[s[p2][0]]-v[s[p1][0]];
if(k<=v0)return ksum(s[p1][0],s[p2][0],l,mid,k);
else return (k-=v0,(sum[s[p2][0]]-sum[s[p1][0]])+ksum(s[p1][1],s[p2][1],mid,r,k));
}
inline ll cksum(int l,int r,int& k)
{
int del=v[r]-v[l];if(k>=del)
{
//printf("trigger spcase! %lld\n",sum[r]-sum[l]);
return (k-=del,sum[r]-sum[l]);
}
return ksum(l,r,0,S,k);
}
inline void clr()
{
for(int i=1;i<=ct;i++)s[i][0]=s[i][1]=0;
for(int i=1;i<=ct;i++)v[i]=0;for(int i=1;i<=ct;i++)sum[i]=0;ct=n;
}
}lt;ll ans[N];struct data{int u;int k;}qr[N];
int we[N];ll wsiz[N];int dfn[N];int nfd[N];int siz[N];
int df;int v[N<<1];int x[N<<1];int ct;int al[N];
struct crr
{
int arr[N*3];int hd;
inline void push(const int& x){
// printf("push %d\n",x);
arr[++hd]=x;}
inline void build()
{
// if(hd==0)return;
sort(arr+1,arr+hd+1);
hd=unique(arr+1,arr+hd+1)-arr-1;
// printf("hd=%d\n",hd);
}
inline int gt(int val)
{
int l=1;int r=hd;
while(l!=r){int mid=(l+r)>>1;if(arr[mid]>=val)r=mid;else l=mid+1;}
return l;
}
}lsh;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
inline ll dfs1(int u,int f)
{
dfn[++df]=u;nfd[u]=df;
for(int i=al[u];i;i=x[i])
if(v[i]!=f)wsiz[u]+=dfs1(v[i],u),siz[u]+=siz[v[i]];
return (siz[u]++,wsiz[u]+=we[u]);
}
inline void solve()
{
int nRG=RG>>1;lsh.hd=0;lt.clr();
for(int i=1;i<=n;i++)
{
// printf("i=%d\n",i);
for(int p=we[dfn[i]],val=0;;p-=val)
{val=p-p/2;if(val>nRG){lsh.push(val);}else break;}
}
lsh.build();S=lsh.hd;if(S==0){RG=nRG;return;}
// printf("solve %d %d,S=%d\n",nRG,RG,S);
//for(int i=1;i<=n;i++)printf("%d ",dfn[i]);printf("\n");
for(int i=1;i<=n;i++)
{
int u=dfn[i];int val=we[u]-(we[u]/2);int cnt=0;
for(int tv=val;(tv>nRG)&&(we[u]-=tv,++cnt);tv=we[u]-(we[u]/2));
if(cnt)lt.ins(i-1,i,0,S,S-lsh.gt(val)+1,cnt,cnt*val);
else lt.cpy(i-1,i);
}
for(int i=1;i<=m;i++)
{
int l=nfd[qr[i].u]-1;int r=nfd[qr[i].u]+siz[qr[i].u]-1;
// printf("l=%d,r=%d\n",l,r);
ans[i]-=lt.cksum(l,r,qr[i].k);
}
// for(int i=1;i<=n;i++)printf("%d ",we[i]);printf("\n");
// for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n");
// for(int i=1;i<=n;i++)printf("%d ",qr[i].k);printf("\n");
// for(int i=1;i<=n;i++)printf("%d ",)
RG=nRG;
}
int main()
{
freopen("shuiti.in","r",stdin);freopen("shuiti.out","w",stdout);
// freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
n=read();m=read();
for(int i=1;i<=n;i++)we[i]=read();
for(int i=1,u,v;i<n;i++)u=read(),v=read(),add(u,v),add(v,u);
dfs1(1,0);
for(int i=1;i<=m;i++)qr[i].u=read(),qr[i].k=read(),ans[i]=wsiz[qr[i].u];
while(RG)solve();
for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;
}
```
## 3.28
## T1
给定$m$维空间当中的若干个点，每个点的每一维坐标有一定的概率是$1,2,3$当中的某一个数字，求所有点对曼哈顿距离的k次幂之和的期望
额其实是是个思博题枚举点对跑个背包就行了
不过我降秩了所以敲了个折半搜索上去，也过了
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=110;typedef long long ll;const ll mod=998244353;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
ll p[N][11][3];int m;int n;int k;ll ch[N][N][11][3];int tr[N];
ll tr1[N][N][N];ll tr2[N][N][N];ll c[N][N];
inline void dfs1(int dep,int lim)
{
// printf("dfs %d %d\n",dep,lim);
if(dep==lim+1)
{
int sum=0;for(int i=1;i<dep;i++)sum+=tr[i];ll tmp;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
tmp=1;for(int t=1;t<=lim;t++)(tmp*=ch[i][j][t][tr[t]])%=mod;
//(tmp*=sum)%=mod;
// printf("tmp=%lld,sum=%d\n",tmp,sum);
for(int t=0;t<=k;t++)
(tr1[i][j][t]+=tmp)%=mod,(tmp*=sum)%=mod;
// for(int t=0;t<=k;t++)printf("%lld ",tr1[i][j][t]);printf("\n");
}return;
}
for(int i=0;i<=2;i++)tr[dep]=i,dfs1(dep+1,lim);
}
inline void dfs2(int dep,int lim)
{
// printf("dfs2 %d %d\n",dep,lim);
if(dep==m+1)
{
int sum=0;for(int i=lim+1;i<=m;i++)sum+=tr[i];ll tmp;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
tmp=1;for(int t=lim+1;t<=m;t++)(tmp*=ch[i][j][t][tr[t]])%=mod;
//(tmp*=sum)%=mod;
// printf("tmp=%lld,sum=%lld\n",tmp,sum);
for(int t=0;t<=k;t++)
(tr2[i][j][t]+=tmp)%=mod,(tmp*=sum)%=mod;
}return;
}for(int i=0;i<=2;i++)tr[dep]=i,dfs2(dep+1,lim);
}
int main()
{
freopen("songfenti.in","r",stdin);freopen("songfenti.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);ll iv=po(1e8,mod-2);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%lld%lld%lld",&p[i][j][0],&p[i][j][1],&p[i][j][2]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int t=0;t<3;t++)(p[i][j][t]*=iv)%=mod;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int k=1;k<=m;k++)
{
ch[i][j][k][0]=(p[i][k][0]*p[j][k][0]%mod+p[i][k][1]*p[j][k][1]%mod+p[i][k][2]*p[j][k][2]%mod)%mod;
ch[i][j][k][1]=(p[i][k][1]*p[j][k][0]%mod+p[i][k][1]*p[j][k][2]%mod+p[i][k][2]*p[j][k][1]%mod
+p[i][k][0]*p[j][k][1]%mod
)%mod;
ch[i][j][k][2]=(p[i][k][0]*p[j][k][2]%mod+p[i][k][2]*p[j][k][0]%mod)%mod;
}
int lim=m/2;dfs1(1,lim);dfs2(lim+1,lim);
ll res=0;
for(int i=0;i<N;i++)
{
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
// for(int i=0;i<=5;i++)
// {
// for(int j=0;j<=5;j++)printf("%lld ",c[i][j]);printf("\n");
// }
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
for(int t=0;t<=k;t++)
(res+=tr1[i][j][t]*tr2[i][j][k-t]%mod*c[k][t])%=mod;
printf("%lld\n",res);return 0;
}
```
## T3
给你一颗树，每次从树上随机ran一对点出来染黑他们之间的路径，求所有点被染黑的期望步数
显然直接上minmax容斥,稍加分析即可发现一个集合对答案的贡献是$(-1)$的若干次幂再乘上总路径条数除上穿过这个点集的路径条数
然后考虑把这个容斥dp出来
可以设$dp(u,v,k)$表示所有点都在u当中，从子树中的点出发到达u的路径当中，有v条不经过任何选中的点，子树中的路径有k条穿过了所选的点集的方案数(其实要配上-1的若干次幂)
这样设计的状态是可以合并的，于是我们大概在$O(n^4)$的时间内解决了这个问题
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=90;const int M=N*(N+1)/2;
typedef unsigned long long ll;const ll mod=998244353;
inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}
int v[N<<1];int x[N<<1];int ct;int al[N];ll tr[N][M];int cnt[N];int n;
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
struct data
{
ll val[M];int hd;
inline ll& operator [](const int& x){return val[x];}
// inline void prit()
/// {
// for(int i=0;i<=hd;i++)printf("%lld ",val[i]);printf("\n");
// }
}dp[N][N];int siz[N];ll ans[M];
inline void mg(data& a,data& b,ll* op,int& cnt,int del)
{
//for(int i=0;i<=a.hd+b.hd+del;i++)op[i]=0;
for(int i=0;i<=a.hd;i++)
for(int j=0;j<=b.hd;j++)(op[del+i+j]+=a[i]*b[j])%=mod;
cnt=max(cnt,a.hd+b.hd+del);
}
inline void cpy(ll* ip,int& cnt,data& a)
{
a.hd=cnt;for(int i=0;i<=cnt;i++)a[i]=ip[i];
for(int i=0;i<=cnt;i++)ip[i]=0;cnt=0;
}
inline void dfs1(int u,int f)
{
for(int i=al[u];i;i=x[i])if(v[i]!=f)dfs1(v[i],u);
dp[u][1].hd=0;dp[u][1][0]=1;dp[u][0].hd=1;dp[u][0][1]=mod-1;
siz[u]=1;
for(int z=al[u];z;z=x[z])
{
if(v[z]==f)continue;int tw=v[z];
for(int i=0;i<=siz[u];i++)
for(int j=0;j<=siz[tw];j++)
{
int del=i*(siz[tw]-j)+j*(siz[u]-i)+(siz[tw]-j)*(siz[u]-i);
int trs=(i==0)?0:i+j;
// printf("%d+%d->%d,del=%d\n",i,j,trs,del);
mg(dp[u][i],dp[tw][j],tr[trs],cnt[trs],del);
}siz[u]+=siz[tw];
for(int i=0;i<=siz[u];i++)cpy(tr[i],cnt[i],dp[u][i]);
}
// printf("fin dp %d\n",u);
// for(int i=0;i<=siz[u];i++)
// {
// printf("tsiz=%d:",i);dp[u][i].prit();
// }
}
int main()
{
freopen("jiandanti.in","r",stdin);freopen("jiandanti.out","w",stdout);
scanf("%d",&n);for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs1(1,0);
for(int i=0;i<=n;i++)
for(int j=1;j<=dp[1][i].hd;j++)(ans[j]+=dp[1][i][j])%=mod;
// for(int j=1;j<=n*(n+1)/2;j++)printf("%lld ",ans[j]);printf("\n");
ll ret=0;
for(int i=1;i<=n*(n+1)/2;i++)(ret+=po(i,mod-2)*(mod-ans[i]))%=mod;
(ret*=n*(n+1)/2)%=mod;printf("%lld",ret);return 0;
}
```
## 3.29
## T2
给定一个长度为$2^n$的数列$f$,使用以下公式计算数组$g$
$$g(i)=\sum_{j=0}^{2^n-1}(popcount((i or j)xor i+1)\mod2)f(j)$$
现在给出$g$希望你还原出$f$
虽然式子很吓人不过你发现g就是f乘了一个特殊点的转移矩阵而已
简单打表发现转移矩阵有规律，然后继续打表发现转移矩阵的逆矩阵还是有规律，仿照fwt的推倒原理发现向量乘这种递归的矩阵可以分治做，于是这题就做完了
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;const int N=2097152+10;
int n;ll b[N];ll a[N];ll c[N];
int main()
{
freopen("b.in","r",stdin);freopen("b.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lld",&b[i]);
if(n==1){printf("%lld",b[0]);return 0;}
if(n==2){printf("%lld %lld",b[0],b[1]-b[0]);return 0;}
for(int i=0;i<n;i++)a[i]=b[i];
for(int i=0;i<n;i+=2){ll a0=a[i];ll a1=a[i+1];a[i]=a0-a1;a[i+1]=a1-a0;}
for(int k=2;k<n;k<<=1)
{
for(int s=0;s<n;s+=(k<<1))
for(int i=s;i<s+k;i++)
{
ll a0=a[i];ll a1=a[i+k];
a[i]=a0+a1;a[i+k]=a1-a0;
}
for(int s=0;s<n;s+=(k<<1))
{
ll t0=b[s+k-1];ll t1=b[s+(k<<1)-1];
a[s]+=t0<<1;a[s+k]+=(t1-t0)<<1;
}
}for(int i=0;i<n;i++)a[i]/=(n/2);ll ret=b[0];
for(int i=1;i<n;i++)ret-=((__builtin_popcount((0|i)^0)+1)&1)*a[i];
a[0]=ret;for(int i=0;i<n;i++)printf("%lld ",a[i]);
}
```
## T3
给定一颗不超过10万个点的树,你有一个沙雕交互接口是给出三个点$a,b,c$询问离这3个点距离之和最小的点是谁
现在要求你在100万询问之内确定树的形态
树是random的，并不是从出题人精心构造的各种数据当中选择一个
正解也是乱搞，每次random两个点间的一条路径，然后切断这条链上的所有边进行分治，确定联通块可以把每一个点都问一遍来确定，而确定链上的点可以把链上的点sort一遍来确定
这样玄学的搞一搞你就win了……
另:sd出题人不会写交互库，现在交互库已经被按在地上摩擦了……
```C
#include<cstdio>
#include<algorithm>
#include "c.h"
#include<map>
#include<vector>
using namespace std;typedef long long ll;
namespace solver
{
const int mN=1e5+10;int srt[mN];int hd;int rotall;
inline bool cmp(const int& x,const int& y)
{
if(x==y)return false;int p=query(rotall,x,y);
if(x==p)return true;else return false;
}
inline void solve(vector <int> cur)
{
if(cur.size()==1)return;if(cur.size()==2){check(cur[0],cur[1]);return;}
map <int,vector <int> > mp;int x;int y;
do{x=rand()%cur.size();y=rand()%cur.size();}while(x==y);
x=cur[x];y=cur[y];hd=0;
for(vector <int> :: iterator it=cur.begin();it!=cur.end();++it)
{
if((*it)==x||(*it)==y)continue;
int lc=query(x,y,*it);mp[lc].push_back(*it);
// printf("qry %d %d %d\n",x,y,*it);
if(*it==lc)srt[++hd]=*it;
}mp[x].push_back(x);mp[y].push_back(y);
rotall=x;sort(srt+1,srt+hd+1,cmp);int lst=x;
// //printf("point between %d ->%d\n",x,y);
// for(int i=1;i<=hd;i++)printf("%d ",srt[i]);printf("\n");
for(int i=1;i<=hd;lst=srt[i],i++)check(lst,srt[i]);check(lst,y);
for(map <int,vector <int> > :: iterator it=mp.begin();it!=mp.end();++it)
solve(it->second);
}
inline void mastersolve(int tot)
{
srand(19260817);vector <int> ve;
for(int i=1;i<=tot;i++)ve.push_back(i);solve(ve);
}
}
void solve(int n){solver::mastersolve(n);}
```
# 3.30
给出一个排列，支持给这个排列一个区间循环移动k步
在每次修改后输出，这个排列的所有轮换当中，逆序对数量最少的是哪一个排列
首先明确一点逆序对个数不可能求出来，因为区间逆序对本身是一个很难的问题
那么我们只能考虑每一次把开头挪到末尾逆序对发生的变化量
这个还是很简单的，设这个数字是x那么贡献就是简单的$n+1-2x$
那么我们把每个数字的权值设成这个，使用splay胡乱维护维护最小前缀和就做完了
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=3*1e5+10;typedef long long ll;
namespace INPUT_SPACE{
const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
char gc() { if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);return (HD==TL)?EOF:*HD++; }
inline int inn()
{
int x,ch,sgn=1;while(((ch=gc())<'0'||ch>'9')&&ch!='-');
if(ch=='-') sgn=-1,x=0;else x=ch^'0';
while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');
return x*sgn;
}
}using INPUT_SPACE::inn;
struct data
{
ll sum;ll mi;int id;
friend data operator +(data a,data b)
{
ll v=a.sum+b.mi;
return (a.mi<=v)?(data){a.sum+b.sum,a.mi,a.id}:(data){a.sum+b.sum,v,b.id};
}
};int n;int q;
struct splaytree
{
int fa[N];int s[N][2];int siz[N];data we[N];data sum[N];int rot;
inline int gc(int x){return s[fa[x]][1]==x;}
inline void ud(int x)
{
sum[x]=(s[x][0])?(sum[s[x][0]]+we[x]):we[x];
sum[x]=(s[x][1])?(sum[x]+sum[s[x][1]]):sum[x];
siz[x]=siz[s[x][0]]+1+siz[s[x][1]];
}inline void rt(int x)
{
int d=fa[x];int t=gc(x);s[d][t]=s[x][t^1];fa[s[x][t^1]]=d;
s[fa[d]][gc(d)]=x;fa[x]=fa[d];s[x][t^1]=d;fa[d]=x;ud(d);
}inline void rtup(int x){rt(gc(x)^gc(fa[x])?x:fa[x]);rt(x);ud(x);}
inline void splay(int x){for(;fa[x]&&fa[fa[x]];rtup(x));if(fa[x])rt(x);rot=x;}
inline int find(int p,int kth)
{
if(kth<=siz[s[p][0]])return find(s[p][0],kth);
if(kth==siz[s[p][0]]+1)return p;
return find(s[p][1],kth-siz[s[p][0]]-1);
}
inline void split(int rk,int nrt,int& rt1,int& rt2)
{
splay(find(nrt,rk));rt1=rot;rt2=s[rot][1];
fa[rt2]=0;s[rot][1]=0;//ud(rt1);
}
inline void shift(int l,int mid,int r)
{
int p1;int p2;int p3;int p4;
split(l,rot,p1,p2),split(mid-(l-1),p2,p2,p3),split(r-mid,p3,p3,p4);
s[p2][1]=p4;fa[p4]=p2;ud(p2);
s[p3][1]=p2;fa[p2]=p3;ud(p3);
s[p1][1]=p3;fa[p3]=p1;ud(p1);rot=p1;
}
inline int crk(int p){splay(p);return siz[s[p][0]];}
inline int build(int l,int r,int* a)
{
if(l>r)return 0;int mid=(l+r)>>1;we[mid]=(data){(n+1)-(a[mid]<<1),(n+1)-(a[mid]<<1),mid};
int ls=build(l,mid-1,a);s[mid][0]=ls;fa[ls]=mid;
int rs=build(mid+1,r,a);s[mid][1]=rs;fa[rs]=mid;
ud(mid);return mid;
}
inline void cbuild(int* a)
{
rot=build(1,n,a);
int p=rot;for(;s[p][0];p=s[p][0]);
int tmp1=n+1;sum[tmp1]=we[tmp1]=(data){0,0,tmp1};siz[tmp1]=1;
s[p][0]=tmp1;fa[tmp1]=p;splay(tmp1);
p=rot;for(;s[p][1];p=s[p][1]);int tmp2=n+2;
sum[tmp2]=we[tmp2]=(data){0,0,tmp2};siz[tmp2]=1;
s[p][1]=tmp2;fa[tmp2]=p;splay(tmp2);
}
}spt;int a[N];
int main()
{
freopen("inversion.in","r",stdin);freopen("inversion.out","w",stdout);
// freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
//scanf("%d%d",&n,&q);
n=inn();q=inn();
for(int i=1;i<=n;i++)///scanf("%d",&a[i]);
a[i]=inn();
spt.cbuild(a);
//for(int i=1;i<=n;i++)printf("%d ",(n+1)-(a[i]<<1));printf("\n");
for(int i=1,l,r,k;i<=q;i++)
{
//scanf("%d%d%d",&l,&r,&k);
l=inn();r=inn();k=inn();
k%=(r-l+1);
if(k!=0)spt.shift(l,l+k-1,r);
printf("%d\n",spt.crk(spt.sum[spt.rot].id));
}return 0;
}
```
## T2
给出一个字符串，至多删去k个子串，使得剩下的字符串字典序最大并且输出
对于字典序最大的问题只有一个做法就是逐位确定，按照字符贪心，假设正在贪心第x个字符，那么我们可以白嫖开头的连续一段x
接下来每选择一段连续的x便会付出1的代价
如果我们的次数还够使那么全选了进入下一轮贪心
否则我们按照连续的x的长度挨个贪心，如果当前长度能全取了那么考虑更小的长度，如果k不够使了，我们希望最后的后缀字典序最大
此时我们知道之前选择的段中最后面的后缀是谁
然后把在这个后缀之前的后缀都当成炮灰，因为选不选他们对答案不造成影响
现在考虑剩下的后缀的当中的最大后缀,和之前的后缀那个大，如果之前的大那么我们尽量选择炮灰，否则马上选那个最大的后缀
然后把剩下的后缀当中在选择的后缀之前的后缀当成炮灰，重复上述的流程即可
实际实现需要一番trick
```C
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;const int N=1e6+10;typedef long long ll;int n;int TOT=0;
template <typename T>inline void gm(T*& bas,int siz,T*& op){op=bas;bas+=siz;}
namespace suffixarray
{
# define pus(x) (sa[cur[a[x]]--]=x)
# define pul(x) (sa[cur[a[x]]++]=x)
# define inds(lms)\
for(int i=1;i<=n;i++)sum[i]=0;for(int i=1;i<=n;i++)sum[a[i]]++;\
for(int i=1;i<=n;i++)sum[i]+=sum[i-1];for(int i=1;i<=n;i++)sa[i]=-1;\
for(int i=1;i<=n;i++)cur[i]=sum[i];for(int i=m;i>=1;i--)pus(lms[i]);\
for(int i=1;i<=n;i++)cur[i]=sum[i-1]+1;\
for(int i=1;i<=n;i++)if(sa[i]>1&&!tp[sa[i]-1])pul(sa[i]-1);\
for(int i=1;i<=n;i++)cur[i]=sum[i];\
for(int i=n;i>=1;i--)if(sa[i]>1&&tp[sa[i]-1])pus(sa[i]-1);
int sum[N];int sa[N];int rk[N];int cur[N];int A_bas[N<<4];int* A_t;
inline void sais(int* a,int n)
{
// printf("sais %d\n",n);
int* tp,*p;gm(A_t,n+1,tp);gm(A_t,n+2,p);tp[n]=1;int m=0;
for(int i=n-1;i>=1;i--)tp[i]=(a[i]==a[i+1])?tp[i+1]:(a[i]<a[i+1]);
for(int i=1;i<=n;i++)rk[i]=(tp[i]&&!tp[i-1])?(p[++m]=i,m):-1;
// for(int i=1;i<m;i++)
// {
// for(int j=p[i];j<=p[i+1];j++)printf("%d ",a[j]<<1|tp[j]);printf("\n");
// }
inds(p);
int *a1;gm(A_t,m,a1);int tot=0;p[m+1]=n;
for(int i=1,x,y;i<=n;i++)
if((x=rk[sa[i]])!=-1)
{
// for(int j=p[x];j<=p[x+1];j++)printf("%d ",a[j]<<1|tp[j]);printf("\n");
if(tot==0||p[x+1]-p[x]!=p[y+1]-p[y])tot++;
else for(int p1=p[x],p2=p[y];p2<=p[y+1];p1++,p2++)
if((a[p1]<<1|tp[p1])!=(a[p2]<<1|tp[p2])){tot++;break;}
a1[y=x]=tot;
}
if(tot==m)for(int i=1;i<=m;i++)sa[a1[i]]=i;else sais(a1,m);
for(int i=1;i<=m;i++)a1[i]=p[sa[i]];inds(a1);
}int tr[N];int a[N];
inline void create_sa(char * mde,int n)
{
for(int i=1;i<=n;i++)tr[mde[i]]=1;tr['a'-1]=1;for(int i='a';i<='z';i++)tr[i]+=tr[i-1];
for(int i=1;i<=n;i++)a[i]=tr[mde[i]];a[++n]=1;sais(a,n);
// for(int i=1;i<=n;i++)printf("%d ",a[i]);printf("\n");
// printf("crete_sa!\n");
// for(int i=1;i<=n;i++)
// {
// printf("sa[%d]=%3d:",i,sa[i]);
// for(int j=sa[i];j<=n;j++)printf("%d ",a[j]);printf("\n");
// }
for(int i=2;i<=n;i++)rk[sa[i]]=i-1;rk[n]=0;
}inline void clear()
{
for(int i='a'-1;i<='z';i++)tr[i]=0;for(int i=1;i<=n+2;i++)rk[i]=0;
for(int* p=A_bas,*ed=A_t+1;p!=ed;++p)(*p)=0;A_t=A_bas;
}
}using namespace suffixarray;char mde[N];int k;
struct data
{
int len;int pos;
friend bool operator <(data a,data b)
{return (a.len==b.len)?a.pos<b.pos:a.len>b.len;}
}qu[N];int hd;int sufmx[N];
inline void subbuild(int l,int r,int mxed)
{
sufmx[r]=r;
for(int i=r-1;i>=l;i--)
if(rk[qu[i].pos]>rk[qu[sufmx[i+1]].pos])sufmx[i]=i;
else sufmx[i]=sufmx[i+1];
int p=l;while(qu[p].pos<mxed&&p<=r)p++;
if(p>r)return;int lst=(rk[qu[sufmx[p]].pos]<rk[mxed])?p:l;
while(p<=r)
reverse(qu+lst,qu+sufmx[p]+1),lst=sufmx[p]+1,p=lst;
// TOT+=r-l;
//for(int p=l;p<=r;p=sufmx[p]+1)reverse(qu+p,qu+sufmx[p]+1);
}
inline void build()
{
sort(qu+1,qu+hd+1);int lst=1;int mxed=0;
for(int i=2;i<=hd;i++)
if(qu[i].len!=qu[i-1].len)
{
int tmp=mxed;mxed=max(mxed,qu[i-1].pos);
subbuild(lst,i-1,tmp);lst=i;
}
subbuild(lst,hd,mxed);
}
inline void solve(int pos,char nw)
{
if(pos>n||nw<'a')return;
if(k==0){for(int i=pos;i<=n;i++)putchar(mde[i]);return;}
while(pos<=n&&mde[pos]==nw)putchar(nw),pos++;hd=0;qu[0].pos=pos;
for(;pos<=n;)
if(mde[pos]!=nw)pos++;
else
{
int cnt=0;while(pos<=n&&mde[pos]==nw)cnt++,pos++;
qu[++hd]=(data){cnt,pos};
}
if(hd<=k)
{
k-=hd;for(int i=1;i<=hd;i++)
for(int z=1;z<=qu[i].len;z++)putchar(nw);
solve(qu[hd].pos,nw-1);return;
}else
{
int mxed=0;build();
// for(int i=1;i<=hd;i++)
// {
// printf("<%d,%d|%d>,",qu[i].len,qu[i].pos,rk[qu[i].pos]);
// }printf("\n");
for(int i=1;i<=k;i++)
{
for(int z=1;z<=qu[i].len;z++)putchar(nw);
mxed=max(mxed,qu[i].pos);
}
//printf("mxed=%d\n",mxed);
for(int i=mxed;i<=n;i++)putchar(mde[i]);return;
}
}
inline void mainsolve(int z)
{
scanf("%d",&k);scanf("%s",mde+1);
// if(z==6806)
// {
// printf("%d %s\n",k,mde+1);
// int tmp;while(1)tmp++;
// }
n=1;while(mde[n+1]!='\0')n++;
create_sa(mde,n);solve(1,'z');putchar('\n');
// printf("TOT=%d\n",TOT);
}
int main()
{
// freopen("tst.txt","r",stdin);freopen("run.txt","w",stdout);
freopen("string.in","r",stdin);freopen("string.out","w",stdout);
A_t=A_bas;
int T;scanf("%d",&T);for(int z=1;z<=T;z++)//printf("%d:",z),
mainsolve(z),clear();
}
```