颓哀 发表于 2025-6-7 10:16:01

AT_abc405

这场比较水了。
A.Is it rated?

手速题,题面大白话照着干就行。
首杀 32s,遥不可及啊。
(嗯这个屑翻译先看一分钟)
#include<bits/stdc++.h>
using namespace std;
int r,x;
int main(){
        cin>>r>>x;
        if(x==1){
                if(1600<=r&&r<=2999)cout<<"Yes";
                else cout<<"No";
        }
        else if(1200<=r&&r<=2399)cout<<"Yes";
        else cout<<"No";
} G.Range Shuffle Query

首先有序列重排数量 \(=\frac{|A|!}{\prod_{x\in A}cnt}\)。
所以我们要维护的:\(cnt\) 前缀和,\(cnt\) 各项阶乘逆元的前缀积(令 \(0!=1\))
看起来也很可以莫队。于是写了一发树状数组+莫队 \(O(N\sqrt{N}\log N)\),不出意料地没过。
莫队是不变的了,考虑干掉 \(\log\),所以我们需要一个 \(O(1)\) 修改的东西。
容易想到对值域分块,\(O(1)\) 修 \(O(\sqrt{N})\) 查,很平衡,然后就过了。
#includeusing namespace std;#define int long longconst int mod=998244353,B=500;int n,Q,a,l,r,x;struct node{        int l,r,x,id;        bool operator < (const node & b) const {                if(l/B!=b.l/B)return lb.r;                return r>Q;        fac=ifac=inv=inv=1;        for(int i=0;ia;fac=fac*i%mod;                if(i>1)inv=mod-mod/i*inv%mod;                ifac=ifac*inv%mod;        }        for(int i=1;i>l>>r>>x;                q={l,r,x,i};        }        sort(q+1,q+Q+1);        for(int i=1,l=1,r=0;iq.l)add(a[--l]);                while(r
页: [1]
查看完整版本: AT_abc405