Codeforces Round 1290 简要题解

A. Mind Control

略

B. Irreducible Anagrams

略

C. Prefix Enlightenment

略

D. Coffee Varieties (hard version)

vp的时候智障的算错了常数，写了一个操作次数$\frac{2n^2}{k}$WA了，然后不想改了（虽然区别不大）。
考虑分治，定义solve(l,r)返回一个$l?r$间的下标集合，使得$[l,r]$中每种不同权值恰好在这个下标集合中对应出现一次。
令$len=r?l+1$，这里有$len=2^c$，当$len=k$的时候我们可以直接$k$次操作求解（每次加入一个看是否出现过，操作完后要清空）。
对于$len>k$的，相当于要合并两个下标集合，其实只需要把两个集合并起来，再删去同时出现在两边的权值的其中一次出现即可。
一个暴力的实现是将左右下标集合各自$\frac{k}{2}$个分一块，每次取出一个左边的块插入所有数字，再取出一个右边的块依次插入看有没有出现过即可（操作完后要清空）。这样单层最多要$\frac{le{n}^2}{k}$次操作，易知总操作次数上界为$\frac{2n^2}{k}$。
考虑稍微优化一下，仍然$\frac{k}{2}$个分一块，但是不急着清空。每次取出左边两个块和右边两个块，先加入左边第一个块，然后插入右边第一个块并查看是否出现过，再插入左边第二个块并查看是否出现过，再插入右边第二个块并查看是否出现过，最后再插一次左边第一个块。这样利用了只保留最后$k$个的特性，不会同时存在自身的两次插入。注意最后剩下的散块要暴力处理。
简单分析可知这样的操作次数上界为$\frac{8n^2}{5}+\mathcal{O}(n)$的，时间复杂度为$\mathcal{O}(n^2)$。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3fusing namespace std;typedef long long ll;int val[1025],q[1000005];
int L=1,R=0;
int vis[1025];int n,k,sz;int query(int y) {
    if (!y) {
    /*L=1;R=0;memset(vis,0,sizeof(vis));return 0;*/puts("R");fflush(stdout);return 0;}else {
    sz++;assert(sz<=(3*n*n)/(2*k));/*bool v=vis[val[y]];vis[val[y]]++;q[++R]=y;if (R-L+1>k) {vis[val[q[L]]]--;L++;}return v;*/printf("? %d\n",y);fflush(stdout);char str[5];scanf("%s",str);return (str[0]=='Y');}
}vector<int> solve(int l,int r) {
    if (r-l+1==k) {
    vector<int> vt;for(int i=l;i<=r;i++)if (!query(i)) vt.push_back(i);query(0);return vt;}int m=((l+r)>>1);vector<int> a=solve(l,m);vector<int> b=solve(m+1,r);bool cur[1025];memset(cur,0,sizeof(cur));for(int i=0;i<a.size();i+=k)for(int j=0;j<b.size();j+=k) {
    if (i+k-1>=a.size()||j+k-1>=b.size()) {
    for(int l=i;l<i+(k>>1)&&l<a.size();l++) query(a[l]);for(int l=j;l<j+(k>>1)&&l<b.size();l++)if (query(b[l])) cur[b[l]]=1;query(0);for(int l=i;l<i+(k>>1)&&l<a.size();l++) query(a[l]);for(int l=j+(k>>1);l<j+k&&l<b.size();l++)if (query(b[l])) cur[b[l]]=1;query(0);for(int l=i+(k>>1);l<i+k&&l<a.size();l++) query(a[l]);for(int l=j;l<j+(k>>1)&&l<b.size();l++)if (query(b[l])) cur[b[l]]=1;query(0);for(int l=i+(k>>1);l<i+k&&l<a.size();l++) query(a[l]);for(int l=j+(k>>1);l<j+k&&l<b.size();l++)if (query(b[l])) cur[b[l]]=1;query(0);}else {
    for(int l=i;l<i+(k>>1);l++) query(a[l]);for(int l=j;l<j+(k>>1);l++)if (query(b[l])) cur[b[l]]=1;for(int l=i+(k>>1);l<i+k;l++)if (query(a[l])) cur[a[l]]=1;for(int l=j+(k>>1);l<j+k;l++)if (query(b[l])) cur[b[l]]=1;for(int l=i;l<i+(k>>1);l++)if (query(a[l])) cur[a[l]]=1;query(0);}}vector<int> vt;for(int i=0;i<a.size();i++)if (!cur[a[i]]) vt.push_back(a[i]);for(int i=0;i<b.size();i++)if (!cur[b[i]]) vt.push_back(b[i]);return vt;
}int main() {
    scanf("%d%d",&n,&k);//for(int i=1;i<=n;i++) scanf("%d",&val[i]);if (k==1) {
    int s=0;for(int i=1;i<=n;i++) {
    bool ok=1;for(int j=i+1;j<=n;j++) {
    query(i);if (query(j)) ok=0;query(0);if (!ok) break;}s+=ok;}printf("! %d\n",s);fflush(stdout);return 0;} vector<int> ans=solve(1,n);printf("! %d\n",(int)ans.size());fflush(stdout);return 0;
} 
/* 4 2 1 4 1 3 */

E. Cartesian Tree

答案等价于计算点对$(i,j)$的数目，使得点$j$在点$i$的子树中。根据笛卡尔树的性质，$j$在$i$的子树中当且仅当在序列上$i$与$j$所在位置之间最大值为$i$。
考虑分治，对于一个最终序列中的区间$[l,r]$，求出$[l,mid]$与$[mid+1,r]$之间的贡献。根据上面的讨论，这里显然只需要关注在区间中的元素，且可以发现一个右边的点$a_j$会在左边的点$a_i$的子树中当且仅当$a_i={\max }_{k=i}^{mid}{a}_k$且$a_i>{\max }_{k=mid+1}^j{a}_k$，反之亦然。那么可以发现一个左边的元素$a_i$会与右边的点有贡献当且仅当它是$[i,mid]$中的最大值，且有贡献的$j$是右边的前缀。
考虑按插入时间从小到大维护对答案的贡献。维护两个从中间向两侧的元素单调栈（即保存左边的后缀最大值和右边的前缀最大值），同时用树状数组维护当前所有元素，支持查询区间元素个数。不放设现在在左边插入了一个最大值$a_x$，那么我们会从左边的单调栈中弹出所有在$x$左侧的后缀最大值，并减去它们在右边的子树大小和，这可以在右边的单调栈中二分出它们在右边的贡献前缀，并用树状数组查询个数完成。同时也要减去右边的前缀最大值对左边的贡献，这部分可以考虑反过来统计，由于$a_i$在右边的祖先数目只跟${\max }_{j=i}^{mid}{a}_j$有关，那么可以对刚刚弹出的后缀最大值划分出的每一段分别计算，用树状数组算出左边的个数，在右边单调栈二分即可。最后还要记得加上$x$在右边的子树大小，也即右边当前元素个数。
时间复杂度为$\mathcal{O}(n{\log }^{2}n)$。

#include <bits/stdc++.h>
#define lowbit(x) (x&-x)using namespace std;typedef long long ll;int sumv[200005];void add(int x,int n,int num) {
    for(;x<=n;x+=lowbit(x)) sumv[x]+=num;
}int sum(int x) {
    int s=0;for(;x;x-=lowbit(x)) s+=sumv[x];return s;
}int sum(int l,int r) {
    return sum(r)-sum(l-1);
}int num[200005],pos[200005],n;
ll ans[200005];int stl1[200005],stl2[200005];
int str1[200005],str2[200005];
int cur[200005];void solve(int l,int r) {
    if (l==r) return;int m=((l+r)>>1);solve(l,m);solve(m+1,r);int top1=0,top2=0,sz=0;for(int i=l;i<=r;i++) cur[++sz]=num[i];sort(cur+1,cur+sz+1);int lsz=0,rsz=0;for(int i=1;i<=sz;i++) {
    int x=cur[i],y=pos[x];if (y<=m) {
    lsz++;int rx=upper_bound(stl2+1,stl2+top1+1,-y)-stl2-1;if (rsz) {
    for(int j=rx+1;j<=top1;j++) {
    int t=upper_bound(str1+1,str1+top2+1,stl1[j])-str1;if (t>top2) ans[x]-=sum(m+1,r);else if (t) ans[x]-=sum(m+1,str2[t]-1); if (t<=top2) ans[x]-=(ll)sum(((j==top1)?l:-stl2[j+1]+1),-stl2[j])*(top2-t+1);}if (rx) {
    int t=upper_bound(str1+1,str1+top2+1,stl1[rx])-str1;if (t<=top2) ans[x]-=(ll)sum(((rx==top1)?l:-stl2[rx+1]+1),y)*(top2-t+1);}ans[x]+=rsz;}top1=rx+1;stl1[top1]=x;stl2[top1]=-y;}else {
    rsz++;int rx=upper_bound(str2+1,str2+top2+1,y)-str2-1;if (lsz) {
    for(int j=rx+1;j<=top2;j++) {
    int t=upper_bound(stl1+1,stl1+top1+1,str1[j])-stl1;if (t>top1) ans[x]-=sum(l,m);else if (t) ans[x]-=sum(-stl2[t]+1,m);if (t<=top1) ans[x]-=(ll)sum(str2[j],((j==top2)?r:str2[j+1]-1))*(top1-t+1);}if (rx) {
    int t=upper_bound(stl1+1,stl1+top1+1,str1[rx])-stl1;if (t<=top1) ans[x]-=(ll)sum(y,((rx==top2)?r:str2[rx+1]-1))*(top1-t+1);}ans[x]+=lsz;}top2=rx+1;str1[top2]=x;str2[top2]=y;}add(y,n,1);}for(int i=l;i<=r;i++) add(i,n,-1);
}int main() {
    scanf("%d",&n);for(int i=1;i<=n;i++) {
    scanf("%d",&num[i]);pos[num[i]]=i;}solve(1,n);for(int i=1;i<=n;i++) ans[i]+=ans[i-1];for(int i=1;i<=n;i++) printf("%lld\n",ans[i]+i);return 0;
}

F. Making Shapes

首先可以发现答案相当于统计所有可表示出的横纵坐标差$\le m$的凸多边形数目。由于没有平行向量，因此只需要考虑每种向量所用的数目。那么可以发现，这等价于统计这样的集合$(c_1,c_2,?,c_n)$的数目（$c_i\ge 0$且$c_i$不全为$0$），使得：
$$?\begin{array}{ll}{\sum }_{x_i>0}{c}_i{x}_i& =?{\sum }_{x_i<0}{c}_i{x}_i\\ {\sum }_{y_i>0}{c}_i{y}_i& =?{\sum }_{y_i<0}{c}_i{y}_i\\ {\sum }_{x_i>0}{c}_i{x}_i& \le m\\ {\sum }_{y_i>0}{c}_i{y}_i& \le m\end{array}$$
原因是这样的每个集合显然能唯一对应一个凸多边形（按方位角排序后依次加入），且不同集合对应的两两不同。
那么转化为一个计数问题，考虑按位DP。令$4$个方向的长度和分别为$sux,sdx,suy,sdy$，那么令$F[i][ux][dx][uy][dy][u][v]$表示考虑了每种向量数目$c$的最后$i$位，且满足$sux$与$sdx$后$i$位相同，$suy$与$sdy$后$i$位相同，$sux,sdx,suy,sdy$分别向前的进位为$ux,dx,uy,dy$，同时$u$与$v$分别表示了$sux$和$suy$的后$i$位是否不超过$m$的后$i$位。令$\max (|x_i|,|y_i|)=w$，题目保证$w\le 4$，那么容易证明任意时刻均有$ux,dx,uy,dy\le nw$。
转移有两种方式，一种是直接$\mathcal{O}(2^n)$枚举所有$c$的第$i$位转移，一种是依次DP每种$c$的第$i$位。理论复杂度上第二种更优秀，但此时$ux,dx,uy,dy$的上界会翻倍，实际效率可能比第一种慢近百倍。
时间复杂度为$\mathcal{O}(2^n{n}^4{w}^4\log m)$或$\mathcal{O}(n^5{w}^4\log m)$。这里的代码是第二种的。

#include <bits/stdc++.h>
#define MOD 998244353using namespace std;typedef long long ll;inline void add(int &x,int y) {
    ((x+=y)>=MOD)?x-=MOD:0;
}int f[2][41][41][41][41][4]; 
int a[10],b[10];int main() {
    int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);int cur=0,up=(n<<3);f[cur][0][0][0][0][0]=1;for(int i=0;i<=30;i++) {
    for(int j=1;j<=n;j++) {
    int ux=((a[j]>0)?a[j]:0),dx=((a[j]<0)?-a[j]:0);int uy=((b[j]>0)?b[j]:0),dy=((b[j]<0)?-b[j]:0);cur^=1;memcpy(f[cur],f[cur^1],sizeof(f[cur]));for(int t1=0;t1<=up;t1++)for(int t2=0;t2<=up;t2++)for(int t3=0;t3<=up;t3++)for(int t4=0;t4<=up;t4++)for(int t5=0;t5<4;t5++)if (f[cur^1][t1][t2][t3][t4][t5]) add(f[cur][t1+ux][t2+dx][t3+uy][t4+dy][t5],f[cur^1][t1][t2][t3][t4][t5]);}bool v=((m>>i)&1);cur^=1;memset(f[cur],0,sizeof(f[cur]));for(int t1=0;t1<=up;t1++)for(int t2=0;t2<=up;t2++)for(int t3=0;t3<=up;t3++)for(int t4=0;t4<=up;t4++) {
    if (((t1^t2)&1)||((t3^t4)&1)) continue;for(int t5=0;t5<4;t5++)if (f[cur^1][t1][t2][t3][t4][t5]) {
    if (!v) add(f[cur][t1>>1][t2>>1][t3>>1][t4>>1][t5|(t1&1)|((t3&1)<<1)],f[cur^1][t1][t2][t3][t4][t5]);else add(f[cur][t1>>1][t2>>1][t3>>1][t4>>1][t5&((t1&1)^((t3&1)<<1))],f[cur^1][t1][t2][t3][t4][t5]);}}}printf("%d\n",(f[cur][0][0][0][0][0]-1+MOD)%MOD);return 0;
}
/* 5 1000000000 -2 4 2 -3 0 -4 2 4 -1 -3 */