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]