A. 魔法
随便写.
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS{
#define ll int
#define lf double
#define ull unsigned ll
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define lbt(x) ((x)&(-(x)))
#define Fill(x,y) memset(x,y,sizeof(x))
#define Copy(x,y) memcpy(x,y,sizeof(x))
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
auto read=[]()->ll{
ll w=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) w=(w<<3)+(w<<1)+(ch^48),ch=getchar();
return cit?w:(-w);
};
} using namespace BSS;
const ll N=1e6+21;
char ch[N];
ll A,B;
ll n,as,bs,ab,ans,tail;
ll val[N],pos[N],vis[N],in[N];
ll L[N],R[N];
ll pre[N][3];
struct I { ll w,id; } p[N];
vector<ll> vec[N];
signed main(){
File(magic);
n=read(),A=read(),B=read(),ab=A+B; scanf("%s",ch+1);
for(ll i=1;i<=n;i++){
val[i]=(ch[i]=='R' ? 1 : 2);
(val[i]&1) ? as++ : bs++ ;
}
if(as*B!=bs*A) puts("NO"),exit(0);
if((as+bs)%(A+B)) puts("NO"),exit(0);
if(A and as%A) puts("NO"),exit(0);
if(B and bs%B) puts("NO"),exit(0);
as=0,bs=0,tail=0;
for(ll i=1;i<=n;i++){
pos[++tail]=i,pre[tail][1]=pre[tail-1][1],pre[tail][2]=pre[tail-1][2];
(val[i]&1) ? (pre[tail][1]++) : (pre[tail][2]++) ;
as=pre[tail][1]-pre[max(tail-ab,0)][1];
bs=pre[tail][2]-pre[max(tail-ab,0)][2];
if(as==A and bs==B){
ans++;
for(ll j=tail-ab+1;j<=tail;j++) vec[ans].push_back(pos[j]),vis[pos[j]]=ans;
tail-=ab;
}
}
puts("YES");
printf("%d\n",ans);
for(ll i=1;i<=n;i++){
if(!in[vis[i]]){
for(auto j : vec[vis[i]]) printf("%d ",j);
in[vis[i]]=1; puts("");
}
}
exit(0);
}
B. 连通性
发现这个题目一开始很难做，因为根本无从下手.
我们考虑一下 \(Floyed\) 算法的实现过程，大概就是有一部分点依靠中间点建立联通关系.
对于一些没有被中间点联通的点对来说，\(AttackedFloyed\) (以下简称 \(AF\))最终跑出来的还是本来就直接联通的点对.
同样设 \(1\) ~ \(n-m\) 的点为黑点，设 \(n-m+1\) ~ \(n\) 的点为白点.
所以我们可以直接发现，对于白点来说，ta 们之间的路径，一定是除了端点之外全部都是黑点.
所以我们就可以来跑 \(dp\) 了，需要用到围绕基准点的思想.
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS{
#define ll long long int
#define lf double
#define ull unsigned ll
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define lbt(x) ((x)&(-(x)))
#define Fill(x,y) memset(x,y,sizeof(x))
#define Copy(x,y) memcpy(x,y,sizeof(x))
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
auto read=[]()->ll{
ll w=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) w=(w<<3)+(w<<1)+(ch^48),ch=getchar();
return cit?w:(-w);
};
} using namespace BSS;
const ll N=105,mod=1e9+7;
ll g[N],pow2[N*N];
ll h[N][N],C[N][N],f[N][N];
auto ksm=[](ll a,ll b,ll c)->ll{
ll w=1; a%=c;
for(;b;b>>=1,a=a*a%c) if(b&1) w=w*a%c;
return w%c;
};
auto PreWork=[]()->void{
for(ll i=0;i<=100;i++){
C[i][0]=1;
for(ll j=1;j<=i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
g[0]=0,pow2[0]=1;
for(ll i=1;i<=10000;i++) pow2[i]=(pow2[i-1]<<1ll)%mod;
for(ll i=1;i<=100;i++){
g[i]=pow2[i*(i-1)>>1];
for(ll j=1;j<=i-1;j++)
g[i]=(g[i]-g[j]*pow2[(i-j)*(i-j-1)>>1]%mod*C[i-1][j-1]%mod+mod)%mod;
}
for(ll i=0;i<=100;i++){
for(ll j=0;j<=100;j++){
h[i][j]=g[j]*ksm(pow2[j]-1,i,mod)%mod*pow2[i*(i-1)>>1]%mod;
}
}
f[1][0]=1,f[0][0]=1,f[1][1]=1;
for(ll n=2;n<=100;n++){
f[n][0]=pow2[n*(n-1)>>1];
for(ll m=1;m<=n;m++){
for(ll i=1;i<=m;i++){
f[n][m]=(f[n][m]+f[n-i][m-i]*C[m-1][i-1]%mod)%mod;
for(ll j=0;j<=n-m;j++)
f[n][m]=(f[n][m]+f[n-i-j][m-i]*C[m-1][i-1]%mod*C[n-m][j]%mod*h[i][j]%mod)%mod;
}
}
}
};
signed main(){
File(floyd);
PreWork(); ll n,m;
for(int Ts=read();Ts;Ts--) n=read(),m=read(),printf("%lld\n",f[n][m]);
exit(0);
}
C. 矩形
首先很自然的就感觉这可能会是个笛卡尔树或者单调栈之类的结构.
我们发现我们如果暴力 \(O(n^2)\) 做的话，空间上也需要存储 \(O(n^2)\) 的数据，于是很难不排除全部存储的想法.
所以考虑排除一些没有用的东西的枚举和储存.
一开始只考虑了对于排名一定大于 \(R\) 的直接不存，也就是维护一个类似于堆的结构，发现还是不行.
观察到 \(R-L+1\le3e5\)，发现这个数据范围是可以接受的，于是考虑也去排除排名小于 \(L\) 的.
一开始考虑了权值线段树，发现面积一定是由 \(a*h\) (底乘高) 构成的，发现 \(a\) 的范围只有 \(1~n\)，感觉很可做.
想着想着就发现我们在这个算法下面是需要分别找到排名位于 \(L\) 和 \(R\) 的权值.
感觉这个东西就是用来二分做的，如果我们能够迅速找到这个权值，那么接下来的东西就都很好做了.
在这个思路下，很容易发现我们还需要在权值线段树下二分，发现复杂度在 \(O(n*logn*logW)\)，于是开始入手.
手玩了一下，发现是个等差数列，线段树直接不需要了，于是复杂度又变成了 \((OlogW)\)，从而就很好写了.
关于二分，我们可以选择二分出排名位于 \(L/R\) 的面积，然后枚举每个点，既然我们的面积已定，如果我们枚举每个点，以这个点为最低的点，从而使高确定，那么底的长度所不大于的限制应该也是确定的.
关于等差数列：(以下用 \(1\) 表示根的位置，用 \(0\) 表示左右儿子所在的区间)
\(eg\): \(00001000000000\)
很难不发现，以在这个区间且经过 \(1\) 的一段连续线段为底的矩形的高都是根的 \(h\) (由于是小根堆)，且底的长度位于不同的长度也有不同的选择方案.
设 \(1\) 及其较短一侧(例子中为左侧)的长度为 \(mn\)，\(1\) 及其较长一侧(例子中为右侧)的长度为 \(mx\)，设当前的底的长度为 \(a\).
例子中的 \(mn\) 等于 \(5\)，\(mx\) 等于 \(10\).
长度位于 \(mx+1\) ~ \(len\) 的 \(a\)，发现最多只能选择 \(len-a+1\) 个，于是等差数列显然.
长度位于 \(mn+1\) ~ \(mx\) 的 \(a\)，最多只能选择 \(mn\) 个，枚举左端点显然.
长度位于 \(1\) ~ \(mn\) 的 \(a\)，最多只能选 \(a\) 个，同样等差数列显然.
于是我们二分的总复杂度就是 \((OlogW)\)，找到了 \(L\) 和 \(R\) 分别位于的权值，那么填数也就很简单了，不再赘述.
C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS{
#define ll long long
#define lf double
#define ull unsigned ll
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define lbt(x) ((x)&(-(x)))
#define Fill(x,y) memset(x,y,sizeof(x))
#define Copy(x,y) memcpy(x,y,sizeof(x))
#define File(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
auto read=[]()->ll{
ll w=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) w=(w<<3)+(w<<1)+(ch^48),ch=getchar();
return cit?w:(-w);
};
} using namespace BSS;
#define ls (x<<1)
#define rs (x<<1|1)
const ll N=6e5+21,inf=1e15;
ll L,R;
ll m,n,cnt,vall,valr,tail,maxn;
ll bin[N<<1],stk[N];
struct I { ll l,r,w,mn,mx,len; } p[N];
auto calc=[](ll x,ll y)->ll{
ll mx=p[x].mx,mn=p[x].mn,len=p[x].len,res=0;
ll z,tmp; y=min(y,len);
if(y>mx) z=y-mx,y=mx,res+=(mn-1+mn-z)*z/2;
if(y>mn) z=y-mn,y=mn,res+=mn*z;
if(y>0) z=y,y=0,res+=z*(z+1)/2;
return res;
};
auto check=[](ll rkw)->ll{
ll x,y,z,rks=0;
for(ll i=1,len;i<=n;i++){
len=rkw/p[i].w,rks+=calc(i,len);
}
return rks;
};
auto getval=[](ll x)->ll{
ll l=0,r=maxn,mid,res;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)>=x) r=mid-1,res=mid;
else l=mid+1;
}
return res;
};
signed main(){
File(rectangle);
n=read(); ll x,y,z,l,r,mn,mx;
for(ll i=1;i<=n;i++){
p[i].w=read(),p[i].l=i,p[i].r=i;
while(tail and p[x=stk[tail]].w>p[i].w){
p[x].r=i-1,tail--;
p[i].l=min(p[i].l,p[x].l);
}
stk[++tail]=i;
}
while(tail) x=stk[tail--],p[x].r=n;
// for(ll i=1;i<=n;i++) cout<<p[i].l<<' '<<p[i].r<<endl;
for(ll i=1;i<=n;i++){
p[i].len=p[i].r-p[i].l+1;
maxn=max(maxn,p[i].w*p[i].len);
p[i].mn=min(i-p[i].l+1,p[i].r-i+1);
p[i].mx=max(i-p[i].l+1,p[i].r-i+1);
}
L=read(),R=read(),vall=getval(L),valr=getval(R);
// printf("%lld\n%lld\n",vall,valr);
vall++,valr--;
for(ll i=1;i<=n;i++){
l=ceil(1.0*vall/p[i].w),r=min(valr/p[i].w,p[i].len);
mn=p[i].mn,mx=p[i].mx;
if(r>mx){
for(ll j=max(mx+1,l);j<=r;j++){
for(ll k=1;k<=p[i].len-j+1;k++){
bin[++cnt]=j*p[i].w; // ~~~
}
}
r=mx;
}
if(r<l) continue;
if(r>mn){
for(ll j=max(mn+1,l);j<=r;j++){
for(ll k=1;k<=mn;k++) bin[++cnt]=j*p[i].w;
}
r=mn;
}
if(r<l) continue;
if(r>0){
for(ll j=max(1ll,l);j<=r;j++){
for(ll k=1;k<=j;k++) bin[++cnt]=j*p[i].w;
}
}
}
// sort(bin+1,bin+1+cnt);
// for(ll i=1;i<=cnt;i++) printf("%lld ",bin[i]);
// puts("");
vall--;
for(ll i=1,lmt=check(vall)-L+1;i<=lmt;i++) bin[++cnt]=vall;
for(ll i=1,lmt=R-check(valr);i<=lmt;i++) bin[++cnt]=valr+1;
sort(bin+1,bin+1+cnt);
for(ll i=1;i<=R-L+1;i++) printf("%lld ",bin[i]);
exit(0);
}