一般Rank
A. string
签。
开始还想复杂了点，后来发现表面上 \(\mathcal{O(n^2)}\) 的复杂度但第二层循环最多跑 26 次，所以事实上复杂度最坏也就 \(\mathcal{O(26n)}\)，显然可过。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define fi first
#define se second
const int Ratio=0;
const int N=5e4+5;
int n;
bool yz[26];
ll ans;
string s;
namespace Wisadel
{
short main()
{
freopen("string.in","r",stdin),freopen("string.out","w",stdout);
ans=n=qr,cin>>s;
fo(i,0,n-1)
{
yz[s[i]-'a']=1;
fo(j,i+1,n-1)
{
if(yz[s[j]-'a']) break;
yz[s[j]-'a']=1,ans++;
}
fo(j,0,25) yz[j]=0;
}
printf("%lld\n",ans);
return Ratio;
}
}
int main(){return Wisadel::main();}
B. subset
想了很久发现不会，于是打了 \(\mathcal{O(2^n)}\) 暴力，拿 20pts。
赛后发现正解其实挺套路的，搞懂之后仅次于 T1 的水。我们可以先将负数变成相反数，记录它们的绝对值和，求解答案时只用减掉这个和即可。这样一个全为非负的序列，先排序，这样除了不选的情况，最小花费就是 \(a_1\)。
我们可以将一个二元组用小根堆存，记其为 \((cost,id)\)，表示考虑到第 \(id\) 个数共花费 \(cost\)。每次更新，我们只需考虑下一个数，即 \(id+1\)，将 \(cost\) 加上它的值，然后考虑是否删去 \(id\) 的两种情况，将它们压入小根堆即可。即将 \((cost+a_{id+1},id+1)\) 和 \((cost+a_{id+1}-a_{id},id+1)\) 这两个二元组压入堆。
分析一下正确性。对于一个二元组 \((cost,id)\)，当取出它时，到 \(id\) 的其他花费小于 \(cost\) 的情况一定全部考虑过了，因为在升序排序下，我们更新的 \(cost+a_{id+1}-a_{id}\) 这个值一定不小于 \(cost\)，也就是说每次更新的二元组的 \(cost\) 一定是不比原来优的，所以不会出现漏选的情况，也保证了答案的升序。而因为我们每次更新相当于是考虑了 \(id\) 这个数选不选的两种情况，而且不会更改之前的选择，因此不会重选。
（可能啰嗦了点但感觉理解一下就好了
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<ll,ll>
#define fi first
#define se second
const int Ratio=0;
const int N=5e5+5;
int n,k;
ll a[N],low;
priority_queue<pii,vector<pii>,greater<pii> >q;
namespace Wisadel
{
short main()
{
freopen("subset.in","r",stdin),freopen("subset.out","w",stdout);
n=qr,k=qr;
fo(i,1,n)
{
a[i]=qr;
if(a[i]<0) a[i]=-a[i],low+=a[i];
}
printf("%lld\n",-low);k--;
sort(a+1,a+1+n);
q.push({a[1],1});
while(k--)
{
pii zc=q.top();q.pop();
printf("%lld\n",zc.fi-low);
if(zc.se<n)
q.push({zc.fi+a[zc.se+1],zc.se+1}),
q.push({zc.fi+a[zc.se+1]-a[zc.se],zc.se+1});
}
return Ratio;
}
}
int main(){return Wisadel::main();}
C. rook
看着有点像二维莫队但不知道怎么转移之后 \(O(1)\) 出答案，最后只拿到了树状数组暴力的 40pts。
学习了 int_R 的莫队套分块的做法，感觉很好理解也比较好写。
以保持列不变，行拼接为例。首先我们可以将图拉成一条直线，这样点的坐标就可以用一个下标来表示。对这些下标进行分块。对于每次询问，我们找到它行范围下的点下标左右边界，以它为新的询问区间排序，然后正常莫队操作。对于范围内的点，我们记录其所在列的点数量，当出现新增一列或删除一列时，进入我们的分块操作。分块所记录的答案为有点的列数，修改时直接让该列答案和所在块答案加或减即可。最后我们查询分块维护的在其列范围内的答案并记录即可。
如此再效仿一次，交换行和列，我们又能得到每次询问的范围内有多少行有点。又根据一个很显然的式子：一次询问的答案等于有点的行数 $\times $ 列宽 \(+\) 有点的列数 \(\times\) 行高 \(-\) 有点的行数 \(\times\) 有点的列数，我们就可以得出每次询问的答案。
莫队复杂度为 \(\mathcal{O(k\sqrt{q})}\) 的，内部分块复杂度是 \(\mathcal{O(q\sqrt{n})}\) 的，总复杂度是 \(\mathcal{O(k\sqrt{q}+q\sqrt{n})}\)。
感觉我写的代码有些累赘，int_R 写的中途交换一次就能少写很多函数%%%。
点击查看代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int,int>
#define fi first
#define se second
const int Ratio=0;
const int N=3e4+5,K=2e5+5;
int n,m,k,q;
int sqk,bl[K],tim[N];
pii p[K];
ll ans[N];
struct rmm
{
int nl,nr,ml,mr,l,r,id;
int wn,wm;
}Q[K];
bool cmp(rmm a,rmm b)
{
if(bl[a.l]==bl[b.l]) return bl[a.l]&1?a.r<b.r:a.r>b.r;
return a.l<b.l;
}
namespace WisB
{
const int sq=175;
int bl[N],v[N],sum[sq],fr[sq];
void Wpre(int X,int Y)
{
fo(i,1,Y) bl[i]=(i-1)/sq+1,v[i]=0;
fo(i,1,bl[Y]) fr[i]=(i-1)*sq+1,sum[i]=0;
}
void Wupd(int x,int k){v[x]+=k,sum[bl[x]]+=k;}
int Wq(int l,int r)
{
int res=0;
if(bl[l]==bl[r])
{
fo(i,l,r) res+=v[i];
return res;
}
fo(i,l,fr[bl[l]+1]-1) res+=v[i];
fo(i,fr[bl[r]],r) res+=v[i];
fo(i,bl[l]+1,bl[r]-1) res+=sum[i];
return res;
}
}
namespace Wisadel
{
void Wadn(int x)
{
int y=p[x].se;
if(!tim[y]) WisB::Wupd(y,1);
tim[y]++;
}
void Wden(int x)
{
int y=p[x].se;
tim[y]--;
if(!tim[y]) WisB::Wupd(y,-1);
}
void Wworkn()
{
WisB::Wpre(n,m);
fo(i,1,q)
{
Q[i].l=lower_bound(p+1,p+1+k,(pii){Q[i].nl,0})-p;
Q[i].r=lower_bound(p+1,p+1+k,(pii){Q[i].nr+1,0})-p-1;
}
sort(Q+1,Q+1+q,cmp);
int l=1,r=0;
fo(i,1,q)
{
while(r<Q[i].r) Wadn(++r);
while(l>Q[i].l) Wadn(--l);
while(r>Q[i].r) Wden(r--);
while(l<Q[i].l) Wden(l++);
Q[i].wn=WisB::Wq(Q[i].ml,Q[i].mr);
}
fo(i,1,m) tim[i]=0;
}
void Wadm(int x)
{
int y=p[x].se;
if(!tim[y]) WisB::Wupd(y,1);
tim[y]++;
}
void Wdem(int x)
{
int y=p[x].se;
tim[y]--;
if(!tim[y]) WisB::Wupd(y,-1);
}
void Wworkm()
{
fo(i,1,k) swap(p[i].fi,p[i].se);
sort(p+1,p+1+k);
WisB::Wpre(m,n);
fo(i,1,q)
{
Q[i].l=lower_bound(p+1,p+1+k,(pii){Q[i].ml,0})-p;
Q[i].r=lower_bound(p+1,p+1+k,(pii){Q[i].mr+1,0})-p-1;
}
sort(Q+1,Q+1+q,cmp);
int l=1,r=0;
fo(i,1,q)
{
while(r<Q[i].r) Wadm(++r);
while(l>Q[i].l) Wadm(--l);
while(r>Q[i].r) Wdem(r--);
while(l<Q[i].l) Wdem(l++);
Q[i].wm=WisB::Wq(Q[i].nl,Q[i].nr);
}
}
short main()
{
freopen("rook.in","r",stdin),freopen("rook.out","w",stdout);
n=qr,m=qr,k=qr,q=qr;
sqk=450;
fo(i,1,k) bl[i]=(i-1)/sqk+1,p[i].fi=qr,p[i].se=qr;
fo(i,1,q) Q[i].id=i,Q[i].nl=qr,Q[i].ml=qr,Q[i].nr=qr,Q[i].mr=qr;
sort(p+1,p+1+k);
Wworkn(),Wworkm();
fo(i,1,q) ans[Q[i].id]=1ll*(Q[i].nr-Q[i].nl+1)*Q[i].wn+1ll*(Q[i].mr-Q[i].ml+1)*Q[i].wm-1ll*Q[i].wn*Q[i].wm;
fo(i,1,q) printf("%lld\n",ans[i]);
return Ratio;
}
}
int main(){return Wisadel::main();}
末
你说得对，但是明天 CSP 第一轮了，今天还在打模拟赛。
但是你说的不对，明天上午还要上 whk。
突袭测试，只打了部分分，虽然没挂，但感觉还应该打得更好。
别的不说了，祝 CPS-S rp++。
完结撒花~
久违的尾图。（感谢假期神
