20181213/14/15刷题日志
shadowice1984
2018-12-15 16:20:10
rt,这里是教练给我留的作业的题解……
写一个日志以免我突然忘记了
## 20181213
### T1:
**bjwc2018餐巾计划问题**
先看题解得到答案对于买的餐巾数目是一个单峰函数，然后大力三分法求函数极值即可
求函数极值的时候先用干净的餐巾然后用慢洗部的餐巾然后用快洗部的餐巾，快洗部的餐巾拿队列维护一下就行了
注意判一下慢洗部的餐巾洗的慢还贵的情况
上代码~
```C
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
using namespace std;const int N=2*1e5+10;typedef long long ll;
int n;int m1;int m2;int c1;int c2;int p;ll sum;int r[N];
struct data{int tim;int val;}q[N];int hd;int tl;
inline ll calc(ll x)
{
ll ret=x*p;ll cle=x;ll mx=0;hd=1;tl=0;
for(int i=1;i<=n;i++)
{
while(hd<=tl&&q[hd].tim<=i-m1)mx+=q[hd].val,hd++;
if(i-m2>=1)q[++tl]=(data){i-m2,r[i-m2]};
int rem=r[i];int del=min((int)cle,rem);rem-=del;cle-=del;
if(rem==0)continue;
del=min((int)mx,rem);rem-=del;mx-=del;ret+=del*c1;
if(rem==0)continue;
while(hd<=tl&&rem)
{
del=min(q[tl].val,rem);rem-=del;q[tl].val-=del;ret+=del*c2;
if(q[tl].val==0)tl--;
}if(rem!=0)return (1LL<<50);
}return ret;
}
int main()
{
scanf("%d%d%d%d%d%d",&n,&m1,&m2,&c1,&c2,&p);
if(m1<m2)swap(m1,m2),swap(c1,c2);if(c1>c2)c1=c2;
for(int i=1;i<=n;i++)scanf("%d",&r[i]);for(int i=1;i<=n;i++)sum+=r[i];
ll l=0;ll r=sum;
while(r-l>3)
{
ll mid1=(2*l+r)/3;ll mid2=(l+r*2)/3;
//printf("[%lld,%lld](%lld,%lld)\n",l,r,mid1,mid2);
ll v1=calc(mid1);ll v2=calc(mid2);
if(v1>=v2)l=mid1;else r=mid2;
}ll ans=(1LL<<50);
for(ll i=l;i<=r;i++)ans=min(ans,calc(i));printf("%lld",ans);return 0;
}
```
### T2
求$[2,n]$之间的所有合数的最小质因子的和$n \leq 9$
使用min_25筛的dp来处理这个问题,我们设$dp(n,j)$表示小于n的质数有+最小质因子大于$P(j)$的合数有几个,然后根据这个数组来统计每个质因子的贡献就可以了
~~或者区间筛+分段打表~~
上代码~
```C
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;const int N=1e5+10;typedef long long ll;
int zhi[N];bool book[N];int ct;int q[N];int lim;int hd;int dp[N];int n;
ll ans;int cnt1[N];int cnt2[N];
int main()
{
ll NANS;
freopen("prime10.out","r",stdin);scanf("%lld",&NANS);printf("%lld\n",NANS);
freopen("prime10.in","r",stdin);
scanf("%d",&n);lim=sqrt(n);
for(int i=2;i<=lim;i++)
{
if(!book[i]){zhi[++ct]=i;}
for(int j=1;j<=ct&&i*zhi[j]<=lim;j++)
{book[i*zhi[j]]=true;if(i%zhi[j]==0)continue;}
}
for(int i=1,r;i<=n;i=r+1){r=n/i;
//printf("%d ",r);
if(r>lim)q[++hd]=r,r=n/r;else break;}//printf("\n");
//for(int i=1;i<=hd;i++)printf("%d ",q[i]);printf("\n");
for(int i=1;i<=lim;i++)cnt1[i]=i-1;for(int i=1;i<=hd;i++)cnt2[i]=q[i]-1;
for(int j=1,t1=hd;j<=ct;j++)
{
ll fv=n/zhi[j];fv=((fv<=lim)?cnt1[fv]:cnt2[n/fv]);dp[j]=fv;
ll lt=zhi[j]*zhi[j];while(lt>q[t1]&&t1)t1--;
for(int i=1;i<=t1;i++)
{ll fv=q[i]/zhi[j];fv=((fv<=lim)?cnt1[fv]:cnt2[n/fv]);cnt2[i]-=fv-j+1;}
for(int i=lim;i>=lt;i--)cnt1[i]-=cnt1[i/zhi[j]]-j+1;
}
// for(int i=1;i<=lim;i++)printf("cnt[%d]=%d\n",i,cnt1[i]);
// for(int i=hd;i>=1;i--)printf("cnt[%d]=%d\n",q[i],cnt2[n/q[i]]);
for(int j=1;j<=ct;j++)
{
//ll fv=n/zhi[j];fv=((fv<=lim)?cnt1[fv]:cnt2[n/fv]);
//printf("val[%d]=%d\n",zhi[j],dp[j]-cnt1[zhi[j-1]]);
ans+=(ll)zhi[j]*(dp[j]-cnt1[zhi[j-1]]);
}printf("%lld\n",ans);
}
```
### T3
bzoj2725……
把s到t的最短路拽出来然后枚举每一条边
发现总是可以松弛路径上的一段区间，扫描线一波就行了
## 20181214
### T1:
您现在要卖盗版光碟，有实用向的和免费版的，您一共要对n个客户卖m次盗版光碟，每个客户有两个参数$a,b$每次询问有一个参数c
如果一个用户的b值大于等于c的话这个客户会使用免费版，您会获得$c×w$的广告费，否则当您给付费版光碟定的价钱$P$小于这个客户的$a$值的时候这个客户会去买付费版的光碟您获得$P$的收益，否则这个客户会十分生气您不会在他身上获得任何收益
对于每一个询问输出最大收益
$$n,m\leq 10^5$$
显然我们可以把客户按照b值排个序，然后将询问离线和客户一起跑双指针形式的插入，现在我们相当于维护一个序列支持动态插点和询问答案的最大值
我们发现价钱应该总是和某个客户的a值相等，不然总是可以通过抬价的方式使得收益更加优秀
那么设$(rk,a)$表示这个点左侧有几个人比他大和这个点的a值，我们事实上就是最大化$rk×a$的值
据说有一个log的高论然而我并不会，我写的是$O(n\sqrt{n})$的分块做法
对于每个块我们其实就是要在整体+add的情况下依然能够快速求出最大值
写一下斜率优化的式子就可以知道是维护一个$(a,rk×a)$的凸包
然后每个块内维护一个单调右移的指针，插入点的时候该重构重构该打标记打标记就行了
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e5+10;const int B=300;typedef long long ll;
struct poi
{
ll x;ll y;
friend poi operator +(poi a,poi b){return (poi){a.x+b.x,a.y+b.y};}
friend poi operator -(poi a,poi b){return (poi){a.x-b.x,a.y-b.y};}
friend bool operator <=(poi a,poi b){return a.y*b.x<=a.x*b.y;}
};int n;int w;int m;int bi[N];int bj[N];ll ans[N];
struct blk
{
poi st[B+3];int tp;int ad;int nw;ll ans;poi a[B+3];bool book[B+3];int siz;
blk(){a[0]=(poi){-0x3f3f3f3f,0};}
inline void cbst()
{
while(nw!=tp&&-ad*(st[nw+1].x-st[nw].x)<(st[nw+1].y-st[nw].y))nw++;
ans=st[nw].y+st[nw].x*ad;
// printf("nw=%d,ans=%lld\n",nw,ans);
}
inline void ins(int pos,const poi& pi)
{
// printf("ins %d %d\n",pi.x,pi.y);
for(int i=1;i<=siz;i++)if(book[i])a[i].y+=a[i].x*ad;ad=0;
for(int i=1;i<pos;i++)if(book[i])a[i].y+=a[i].x;
a[pos]=pi;book[pos]=true;tp=0;
for(int i=1;i<=siz;i++)
{
if(!book[i])continue;
if(a[i].x==a[i-1].x)continue;
while(tp>1&&(st[tp]-st[tp-1])<=(a[i]-st[tp-1]))tp--;st[++tp]=a[i];
}nw=1;cbst();
}inline void mov(){ad++;cbst();}
}bl[N/B+3];
struct treearray
{
int ta[N];
inline void c(int x){for(;x;x-=x&(-x))ta[x]++;}
inline int q(int x){int r=0;for(;x<=n;x+=x&(-x))r+=ta[x];return r;}
}ta;
struct data{int a;int b;int nu;}a[N];
inline bool cmp1(const data& a,const data& b){return a.a<b.a;}
inline bool cmp2(const data& a,const data& b){return a.b<b.b;}
struct qry
{int c;int fr;friend bool operator <(qry a,qry b){return a.c<b.c;}}qr[N];
inline void ins(const data& pi)
{
// printf("ins %d %d\n",pi.a,pi.b);
ta.c(pi.nu);for(int i=1;i<bi[pi.nu];i++)bl[i].mov();
bl[bi[pi.nu]].ins(bj[pi.nu],(poi){pi.a,(ll)ta.q(pi.nu)*pi.a});
}
int main()
{
// system("fc tst.txt e10.out");
//freopen("e10.in","r",stdin);freopen("tst.txt","w",stdout);
scanf("%d%d",&n,&w);
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<bi[n];i++)bl[i].siz=B;bl[bi[n]].siz=((n%B)?n%B:B);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i].a,&a[i].b);sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)a[i].nu=i;sort(a+1,a+n+1,cmp2);scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",&qr[i].c),qr[i].fr=i;sort(qr+1,qr+m+1);
for(int i=1,j=1;i<=m;i++)
{
while(j<=n&&a[j].b<qr[i].c)ins(a[j]),j++;ll ret=0;
for(int k=1;k<=bi[n];k++)ret=max(ret,bl[k].ans);
ans[qr[i].fr]=ret+(ll)qr[i].c*(n-j+1)*w;
// printf("ans[%d]=%lld+%lld\n",qr[i].c,ret,(ll)qr[i].c*(n-j+1)*w);
}for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);return 0;
}
```
### T3:
给定一堆串，对于每一个串有一个询问参数$k_{i}$，现在你要对每一个串输出包含这个串作为后缀的字符串集合当中的第$k_{i}$小标号，无解输出-1
$n \leq 10^5, \Sigma|S|\leq3×10^5$
这个人太菜了，他写了一个广义sam+倍增+线段树合并……
其实反过来跑trie之后就是dfs序上区间第k大了，主席树就行了，懒一些的话可以trie上跑线段树合并
```C
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;const int N=1e5+10;const int M=3*1e5+10;int n;
struct linetree
{
int s[22*N][2];int v[22*N];int ct;
inline void ins(int p,int l,int r,int pos)
{
v[p]++;if(r-l==1)return;int mid=(l+r)/2;
if(pos<=mid)ins(s[p][0]=s[p][0]?s[p][0]:++ct,l,mid,pos);
else ins(s[p][1]=s[p][1]?s[p][1]:++ct,mid,r,pos);
}
inline void mg(int p1,int p2)
{
if(s[p1][0]&&s[p2][0])mg(s[p1][0],s[p2][0]);else if(s[p2][0])s[p1][0]=s[p2][0];
if(s[p1][1]&&s[p2][1])mg(s[p1][1],s[p2][1]);else if(s[p2][1])s[p1][1]=s[p2][1];
v[p1]=v[s[p1][0]]+v[s[p1][1]];
}
inline int kth(int p,int l,int r,int k)
{
if(k>v[p])return -1;if(r-l==1){return r;}int mid=(l+r)/2;
if(k<=v[s[p][0]])return kth(s[p][0],l,mid,k);
else return kth(s[p][1],mid,r,k-v[s[p][0]]);
}
}lt;int rot[2*M];int pre[N];int ans[N];int fa[2*M][22];int len[2*M];
struct qry{int k;int fr;};vector <qry> qr[2*M];int strl[N];
int v[2*M];int x[2*M];int al[2*M];int ct;char mde[M];
inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;}
struct suffixautomaton
{
int mp[2*M][30];int fa[2*M];int ct;suffixautomaton(){ct=1;}
inline void ins(int& p,int c)
{
int t;int nw;int q;
if(mp[p][c])
{
q=mp[p][c];if(len[q]==len[p]+1)goto ret;len[++ct]=len[p]+1;
for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i];
for(t=p;t&&mp[t][c]==q;t=fa[t])mp[t][c]=ct;fa[ct]=fa[q];fa[q]=ct;
}else
{
nw=++ct;len[nw]=len[p]+1;
for(t=p;t&&mp[t][c]==0;t=fa[t])mp[t][c]=nw;
if(t==0){fa[nw]=1;goto ret;}q=mp[t][c];
if(len[q]==len[t]+1){fa[nw]=q;goto ret;}len[++ct]=len[t]+1;
for(int i=1;i<=26;i++)mp[ct][i]=mp[q][i];
for(;t&&mp[t][c]==q;t=fa[t])mp[t][c]=ct;
fa[ct]=fa[q];fa[nw]=fa[q]=ct;
}ret:p=mp[p][c];
}
inline void build(){for(int i=2;i<=ct;i++)add(fa[i],i);}
}sam;
inline void pred(int u)
{
for(int i=0;fa[u][i];i++)fa[u][i+1]=fa[fa[u][i]][i];
for(int i=al[u];i;i=x[i])fa[v[i]][0]=u,pred(v[i]);
}
inline int dfs(int u)
{
int ret=rot[u];
for(int i=al[u];i;i=x[i])
{int vp=dfs(v[i]);if(ret==-1)ret=vp;else if(vp!=-1)lt.mg(ret,vp);}
vector <qry> :: iterator it;
for(it=qr[u].begin();it!=qr[u].end();++it)
ans[it->fr]=lt.kth(ret,0,n,it->k);return ret;
}
int main()
{
system("fc password9.out tst.txt");return 0;
//freopen("password9.in","r",stdin);freopen("tst.txt","w",stdout);
scanf("%d",&n);
for(int i=1;i<=2*M-10;i++)rot[i]=-1;
for(int i=1;i<=n;i++)
{
scanf("%s",mde+1);int p=1;int j=1;
for(;mde[j]!='\0';j++)sam.ins(p,mde[j]-'a'+1);strl[i]=j-1;
rot[p]=(rot[p]==-1)?++lt.ct:rot[p];lt.ins(rot[p],0,n,i);pre[i]=p;
}sam.build();pred(1);
for(int i=1,k;i<=n;i++)
{
int p=pre[i];for(int j=20;j>=0;j--)
if(fa[p][j]&&len[fa[p][j]]>=strl[i])p=fa[p][j];scanf("%d",&k);
qr[p].push_back((qry){k,i});
}dfs(1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0;
}
```
## 20181215
### T1:
team work的2e5版本
之前有一篇博客专门讲斯特林数转下降幂的，这题只需要ntt一波把斯特林数刷出来就行了
上代码~
```C
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1048576+10;typedef unsigned long long ll;
const ll mod=998244353;int n;int m;;ll fac[N];ll ifac[N];int rv[N];ll rt[2][22];
ll st[N];ll f[N];ll g[N];
# define md(x) (x=(x>mod)?(x-mod):x)
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 void ntt(ll* a,int len,int o)
{
for(int i=0;i<len;i++)if(i<rv[i])swap(a[i],a[rv[i]]);
for(int k=1,j=1;k<len;k<<=1,j++)
for(int s=0;s<len;s+=(k<<1))
for(int i=s,w=1;i<s+k;i++,w=w*rt[o][j]%mod)
{ll a1=a[i+k]*w%mod;a[i+k]=a[i]+mod-a1,md(a[i+k]),a[i]+=a1,md(a[i]);}
if(o){ll iv=po(len,mod-2);for(int i=0;i<len;i++)(a[i]*=iv)%=mod;}
}
int main()
{
ll NANS;
freopen("out10.out","r",stdin);scanf("%lld",&NANS);printf("%lld\n",NANS);
freopen("in10.in","r",stdin);
for(int i=1,t=(mod-1)/2;i<=20;i++,t>>=1)rt[0][i]=po(3,t);
for(int i=1,t=(mod-1)/2;i<=20;i++,t>>=1)rt[1][i]=po(332748118,t);
scanf("%d%d",&n,&m);int len=1;int d=0;for(;len<=m;len<<=1,d++);len<<=1;d++;
ifac[0]=1;ifac[1]=1;for(int i=2;i<=m;i++)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod;
for(int i=1;i<=m;i++)(ifac[i]*=ifac[i-1])%=mod;
for(int i=0;i<len;i++)rv[i]=(rv[i>>1]>>1)|((i&1)<<(d-1));
for(int i=0;i<=m;i++)f[i]=(i&1)?(mod-ifac[i])%mod:ifac[i];
for(int i=0;i<=m;i++)g[i]=po(i,m)*ifac[i]%mod;
// for(int i=0;i<=m;i++)printf("%lld ",f[i]);printf("\n");
// for(int i=0;i<=m;i++)printf("%lld ",g[i]);printf("\n");
ntt(f,len,0);ntt(g,len,0);
for(int i=0;i<len;i++)st[i]=(f[i]*g[i])%mod;ntt(st,len,1);
// for(int i=0;i<len;i++)printf("%lld ",st[i]);printf("\n");
ll ans=0;ll pw=1;
for(int i=0;i<=min(n,m);(pw*=(n-i))%=mod,i++)
(ans+=st[i]*pw%mod*po(2,n-i))%=mod;printf("%lld\n",ans);
}
```
### T2:
FJOI2017矩阵填数，只是将矩阵改成了1行n列并且将限制条件加到了500个
把每个值域单独算一下的大思路依然没变，现在只需要考虑如何解决相同值域的问题，发现就算这个值域块是零散的我们依然可以强行把值域块压缩到一起使得这个问题变成一个所有限制的v值都是一样的子问题
接下来我们考虑去重的问题，显然非多项式算法的容斥原理已经做不了这题了，因此我们放弃容斥而是采用最小标号计数的方式来去重，对于一个方案我们仅仅考虑最左侧的最大值
那么我们会发现对于两个区间如果一个包含另一个，那么两个区间的右端点可以被调整到一致，这个可以自己画个图理解一下，因为如果大区间在后面被满足的话小区间就直接gg了因此大区间的后半部分可以被删掉
那么我们可以将区间按照左端点排序然后右端点取后缀min，此时右端点随着左端点是单调的，那么我们会发现任意时刻满足的限制总是一段前缀，设$dp(i,j)$表示决策到第i个块并且满足了前j个限制的方案数即可大力dp求解
复杂度$O(n^2logn)/O(n^2)$
上代码~
```C
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int N=1e3+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;}
int n;int m;int q;map <int,int> mp,mp1;int S;int S1;int T;int lim[N];
struct data{int nu;int len;}q1[N][N];int hd1[N];
struct qry
{
int l;int r;
friend bool operator <(qry a,qry b){return (a.l==b.l)?a.r>b.r:a.l<b.l;}
}q2[N][N];int hd2[N];ll dp[N][N];int mx[N];
inline ll calc(data* a,qry* aq,int hd1,int hd2,int lim)
{
// printf("calc %d\n",lim);
// printf("dot1:");for(int i=1;i<=hd1;i++)printf("(%d %d),",a[i].nu,a[i].len);printf("\n");
// printf("line1:");for(int i=1;i<=hd2;i++)printf("(%d,%d),",aq[i].l,aq[i].r);printf("\n");
for(int i=1;i<=hd2;i++)
{
int nmi=0x3f3f3f3f;int nmx=-1;
for(int j=1;j<=hd1;j++)
if(aq[i].l<=a[j].nu&&a[j].nu<=aq[i].r)nmi=min(nmi,j),nmx=max(nmx,j);
if(nmi>nmx)return 0;aq[i].l=nmi;aq[i].r=nmx;
}for(int i=1;i<=hd1;i++)a[i].nu=i;sort(aq+1,aq+hd2+1);
for(int i=hd2-1;i>=1;i--)aq[i].r=min(aq[i].r,aq[i+1].r);
// printf("dot2:");for(int i=1;i<=hd1;i++)printf("(%d %d),",a[i].nu,a[i].len);printf("\n");
// printf("line2:");for(int i=1;i<=hd2;i++)printf("(%d,%d),",aq[i].l,aq[i].r);printf("\n");
for(int i=1;i<=hd1;i++)mx[i]=0;
for(int i=1;i<=hd1;i++)
for(int j=hd2;j>=1;j--)if(aq[j].l<=a[i].nu&&a[i].nu<=aq[j].r){mx[i]=j;break;}
for(int i=0;i<=hd1;i++)for(int j=0;j<=hd2;j++)dp[i][j]=0;dp[0][0]=1;
for(int i=0;i<hd1;i++)
for(int j=0;j<=hd2;j++)
{
if(dp[i][j]==0)continue;ll fv=po(lim,a[i+1].len);
(dp[i+1][max(j,mx[i+1])]+=dp[i][j]*(fv+mod-po(lim-1,a[i+1].len)))%=mod;
if(j==hd2||aq[j+1].r>i+1)
(dp[i+1][j]+=dp[i][j]*po(lim-1,a[i+1].len))%=mod;
}
// printf("ans=%lld\n",dp[hd1][hd2]);
return dp[hd1][hd2];
}
struct nod{int l;int r;int lim;}lt[N];int val[N];
inline void solve()
{
scanf("%d%d%d",&n,&m,&q);mp1[1]=1;mp1[n+1]=1;
for(int i=1;i<=q;i++)scanf("%d%d%d",<[i].l,<[i].r,<[i].lim);
for(int i=1;i<=q;i++)mp1[lt[i].l]=1,mp1[lt[i].r+1]=1,mp[lt[i].lim]=1;
map <int,int> :: iterator it,it1;
for(it=mp.begin(),it1=it,++it1;it1!=mp.end();++it,++it1)it1->second+=it->second;
for(it=mp.begin();it!=mp.end();++it)lim[it->second]=it->first;S=mp.size();
for(it=mp1.begin(),it1=it,++it1;it1!=mp1.end();++it,++it1)it1->second+=it->second;
for(int i=1;i<=q;i++)lt[i].l=mp1[lt[i].l],lt[i].r=mp1[lt[i].r+1]-1;S1=mp1.size();
// printf("line:\n");
// for(int i=1;i<=q;i++)
// {
// printf("%d %d\n",lt[i].l,lt[i].r);
// }
for(int i=1;i<=S1;i++)val[i]=0x3f3f3f3f;
for(int i=1;i<=q;i++)
for(int j=lt[i].l;j<=lt[i].r;j++)val[j]=min(val[j],lt[i].lim);
int k=1;ll ans=1;
for(it=mp1.begin(),it1=it,++it1;it1!=mp1.end();++it,++it1,k++)
if(val[k]==0x3f3f3f3f)(ans*=po(m,(it1->first-it->first)))%=mod;
else {int t=mp[val[k]];q1[t][++hd1[t]]=(data){k,it1->first-it->first};}
for(int i=1;i<=q;i++)
{int t=mp[lt[i].lim];q2[t][++hd2[t]]=(qry){lt[i].l,lt[i].r};}
for(int i=1;i<=S;i++){(ans*=calc(q1[i],q2[i],hd1[i],hd2[i],lim[i]))%=mod;}
printf("%lld\n",ans);
}
inline void clear()
{
for(int i=1;i<=S;i++)hd1[i]=0;for(int i=1;i<=S;i++)hd2[i]=0;
mp.clear();mp1.clear();
}
int main(){
//system("fc filling10.ans tst.txt");return 0;
//freopen("filling10.in","r",stdin);freopen("tst.txt","w",stdout);
scanf("%d",&T);for(int i=1;i<=T;i++)solve(),clear();return 0;}
```