赛时 rank 38,T1 20,T2 50,T3 0,T4 0
T2 挂分原因 : 莫队n，m写反了，但样例中这俩一样，遂寄
T1 九次九日九重色
\[\color{Green}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Red}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Blue}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Yellow}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Pink}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Orange}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Purple}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{#66CCFF}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]\[\color{Brown}{\Huge{！！！！！！！！！九日\,！！！！！！！！！}} \]不用数了正好九个
玩galgame有啥意思不如玩我们nine suns
调和级数预处理出每个数的倍数，时间复杂度\(O(n\log n)\)
然后就是求一个在二维平面上的最长上升子序列
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10;
int n,a[N],b[N],sum[N];
vector<int> can[N];
inline void pre_work(){
for(int i = 1;i <= n; ++i){
for(int j = i;j <= n;j += i){
can[i].push_back(j);
}
}
}
int ans = 0;
class BIT{
private:
int tree[N];
#define lowbit(x) (x&(-x))
public:
int mx = 0;
inline void update(int pos,int val){
for(int i = pos;i <= mx;i += lowbit(i)) tree[i] = max(val,tree[i]);
}
inline int query(int pos){
int res = 0;
for(int i = pos; i;i -= lowbit(i)) res = max(tree[i],res);
return res;
}
}T;
int posa[N],posb[N];
inline void solve(){
cin>>n;
for(int i = 1;i <= n; ++i) cin>>a[i],posa[a[i]] = i;
for(int i = 1;i <= n; ++i) cin>>b[i],posb[b[i]] = i;
pre_work();T.mx = n;
for(int i = 1;i <= n; ++i){
vector<pair<int,int> > p;
for(auto j : can[a[i]]){
p.push_back(make_pair(posb[j],T.query(posb[j]-1)+1));
}
for(auto j : p) T.update(j.first,j.second);
}
for(int i = 1;i <= n; ++i) ans = max(ans,T.query(i));
cout<<ans;
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T2 天色天歌天籁音
是道莫队水题
先离散化
记录一下一个数出现的次数和所有数出现次数的出现次数即可
可能有点离谱。
就随便拿个样例说一下
1 2 3 4 4 5 6
如上，我们要求\(l = 2,r = 6\)
那么\(cnt_1 = 0,cnt_2 = 1,cnt_3 = 1,cnt_4 = 2,cnt_5 = 1,cnt_6 = 1\)
还有\(tot_0 = 1,tot_1 = 4,tot_2 = 1,tot_3 = tot_4 = tot_5 = tot_6 = 0\)
如果从\(l=2,r=6\)转移到\(l=2,r=3\)
当右指针从5移动到4时，那么就有\(cnt_4=1\)，那么\(tot_2=1\)
我们发现，每次转移，答案至多会更改1
若最大的出现次数减没，则最优答案就是最大次数减一，若有更大的，更新。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 2e5 + 10;
int n,m,a[N],pos[N],L[N],R[N],len,ans[N];
vector<int> num;
struct Query{int id,l,r;}q[N];
int cnt[N],tot[N];
inline void solve(){
cin>>n>>m;
for(int i = 1;i <= n; ++i) cin>>a[i],num.emplace_back(a[i]);
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
for(int i = 1;i <= n; ++i)
a[i] = lower_bound(num.begin(),num.end(),a[i])-num.begin()+1;
len = sqrt(n);
for(int i = 1;i <= len; ++i) L[i] = R[i - 1] + 1,R[i] = i * len;
if(R[len] < n) R[len] = n;
for(int i = 1;i <= len; ++i) for(int j = L[i];j <= R[i]; ++j) pos[j] = i;
for(int i = 1;i <= m; ++i) cin>>q[i].l>>q[i].r,q[i].id = i;
sort(q+1,q+1+m,[](Query x,Query y){return pos[x.l] == pos[y.l]?(pos[x.l]&1?x.r>y.r:x.r<y.r):x.l<y.l;});
int left = 1,right = 0,res = 0;
tot[0] = num.size();
for(int i = 1;i <= m; ++i){
int l = q[i].l,r = q[i].r;
while(left < l){
if(cnt[a[left]] >= 0) tot[cnt[a[left]]]--;
if(cnt[a[left]] > 0) tot[cnt[a[left]]-1]++;
if(res == cnt[a[left]] && !tot[cnt[a[left]]]) res--;
cnt[a[left]]--;
left++;
}
while(right < r){
right++;
if(cnt[a[right]] >= 0) tot[cnt[a[right]]]--;
cnt[a[right]]++;
if(cnt[a[right]] >= 0) tot[cnt[a[right]]]++;
res = max(res,cnt[a[right]]);
}
while(left > l){
left--;
if(cnt[a[left]]) tot[cnt[a[left]]]--;
cnt[a[left]]++;
tot[cnt[a[left]]]++;
res = max(res,cnt[a[left]]);
}
while(right > r){
if(cnt[a[right]]) tot[cnt[a[right]]]--;
if(cnt[a[right]] > 0) tot[cnt[a[right]]-1]++;
if(res == cnt[a[right]] && !tot[cnt[a[right]]]) res--;
cnt[a[right]]--;
right--;
}
ans[q[i].id] = res;
}
for(int i = 1;i <= m; ++i) cout<<-ans[i]<<'\n';
}
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
solve();
}
T3 春色春恋春熙风
Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
Dsu On Tree
今天学这个，T4不改了
T4 雪色雪花雪余痕
难
标签：cnt,right,16,int,tot,csp,using,集训,left From： https://www.cnblogs.com/hzoi-Cu/p/18349067