[省选集训2022] 模拟赛16
小Z与函数
题目描述
在 \(2022/3/24\) 上午，\(\tt zxy\) 看到了一个函数：
int get(int n)
{
int res=0;
for(int i=1;i<=n;i++)
{
int vs=0;
for(int j=i;j<=n;j++) if(a[i]有一个长度为 \(n\) 的序列 \(a\)，对于 \(a\) 的每个前缀，将其作为一个序列 \(a\) 所求得的函数值是多少？
\(T\leq 5,1\leq n\leq 2\cdot 10^5,1\leq a_i\leq n\)
解法
社论：我都会做的题一定是垃圾题。我们可以把总次数分成 \(\tt swap\) 和 \(\tt vs\) 两部分分别解决。
首先考虑 \(\tt swap\) 的次数，其实就是每个点前面比它小的值的个数之和（相同的值要去重），不难证明。
然后发现这个 \(\tt vs\) 很难做，好像单次计算都要 \(O(n^2)\)，那么我们不妨先考虑如何动态插入，达成总时间复杂度 \(O(n^2)\) 的目标。考虑新加入的数对前面的影响，因为选择排序原来是选出一个极长上升子序列，然后做这样的变化：
上图分别展示了，正常选择排序时的变化，和我们在序列末尾插入（用红点表示）对前面的影响。从插入的角度看，我们是选出一个极长下降子序列（首项为第一个 \(<\) 插入值的数），然后子序列对应的位置都会产生一次交换。
如果你理解了上面的过程，就不难写出 \(O(n^2)\) 的优秀算法：
for(int i=1;i<=n;i++)
{
for(int j=1;j取出一个极长下降子序列是很难得，但是考虑到每个位置只会被覆盖一次，我们考虑使用势能法，把未覆盖的位置作为势能来让复杂度正确。有一个关键的 \(\tt observation\) 是，如果某个值 \(x\) 在极长下降子序列中去覆盖某个位置，而这个位置先前已经被覆盖过的话，\(x\) 的覆盖以后都不起作用。因为这样一定是存在一个比 \(x\) 小的数先前就把这个位置覆盖过，那么这个较小数一定抢先覆盖了所有 \(x\) 未来所有可能覆盖到的位置。
所以我们维护一个关于值的 \(\tt set\)，每次暴力扫描，用树状数组维护排名，那么要么删除这个值，要么覆盖一个位置。根据势能法，时间复杂度 \(O(n\log n)\)，代码实现极为简洁。
#include
#include
#include
#include
#include
using namespace std;
const int M = 200005;
#define ll long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
void write(ll x)
{
if(x>=10) write(x/10);
putchar(x%10+'0');
}
int T,n,a[M],b[M],use[M];
struct fenwick
{
int b[M];
fenwick() {memset(b,0,sizeof b);}
void clear() {memset(b,0,sizeof b);}
void add(int x)
{
for(int i=x;i<=n;i+=i&(-i)) b[i]++;
}
int ask(int x)
{
int r=0;
for(int i=x;i>0;i-=i&(-i)) r+=b[i];
return r;
}
}A,B;
void work()
{
n=read();long long ans=0;
set s;A.clear();B.clear();
for(int i=1;i<=n;i++)
a[i]=read(),b[i]=use[i]=0;
for(int i=1;i<=n;i++)
{
vector d;
for(auto &x:s)
{
if(x>=a[i]) break;
int p=i-B.ask(x);
if(!b[p]) b[p]=1,ans++;
else if(b[p]) d.push_back(x);
}
for(auto &x:d) s.erase(x);
int y=a[i];ans+=A.ask(y-1);
if(!use[y])
s.insert(y),A.add(y),use[y]=1;
B.add(y);
write(ans),putchar(' ');
}
puts("");
}
signed main()
{
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
T=read();
while(T--) work();
}