C
令\(x=i\times j\)，\(f(x)=p=(i\times j)^2=x^2\)（\(i,j\geq 1\)），\(f(x)\)的所有取值構成可重集和\(S\)，同時\(S\)為單調不減的，現在求\(S\)中前\(k\)小的元素之和。
因為\(k\)比較大，顯然我們不能直接暴力枚舉。我們嘗試模擬一下會發現：
x=1,(i,j)組合1種
x=2,(i,j)組合2種
x=3,(i,j)組合2種
......
x=v,(i,j)組合等於cnt[fac[v]]
也就是x=v的(i,j)組合數等於x的因數個數令\(g(x)=\sum_{i=1}^x{cnt[i]}\)，其中\(cnt[i]\)表示\(i\)的因數個數。我們需要找到最大的那個\(x\)，滿足\(g(x)\leq k\)，這個可以通過二分答案，然後每次\(check\)使用分塊解決，時間複雜度為\(O(\sqrt{V}\log {V})\)。
找到上界後，我們需要解決\(\sum_{i=1}^{x}{i^2\times cnt[i]}\)，也就是\(\sum_{i=1}^{x}\sum_{d=1}^{i}{i^2}\times [d\mid i]\)，如果這樣寫表示每次枚舉數\(num\)，然後枚舉其因數，時間複雜度為\(O(V\times \sqrt{V})\)，顯然會爆掉。
我們交換一下枚舉順序：\(\sum_{d=1}^{x}\sum_{k=1}^{\lfloor\frac{x}{d}\rfloor}{(kd)^2}=\sum_{d=1}^{x}d^2\sum_{k=1}^{\lfloor\frac{x}{d}\rfloor}{k^2}\)，令\(m=\lfloor\frac{x}{d}\rfloor\)，那麼\(\sum_{k=1}^{m}{k^2}=\frac{n\times (n+1)\times(2\times n+1)}{6}\)。
我們可以根據\(d\)對\(\lfloor\frac{x}{d}\rfloor\)進行分塊，也就是\(\lfloor\frac{x}{l}\rfloor=\lfloor\frac{x}{r}\rfloor\)，然後對於相同的\(m\)，令\(h(x)=\sum_{i=1}^x{i^2}\)，式子變為\(\sum{(h(r)-h(l-1)\times h(m))}\)。
注意要及時取模就好，最後我們再加上\((k-g(x))\times x^2\)就好。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 998244353;
//求[1,n]的約數個數之和
int inv_6;
int f(int n){
int sum=0;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
sum+=n/l*(r-l+1);
}
return sum;
}
int ksm(int b,int p){
int res=1;
while(p){
if(p&1) res=res*b%mod;
b=b*b%mod;
p>>=1;
}
return res;
}
//g(n)為[1,n]所有數平方和
int g(int n){
return n%mod*(n%mod+1)%mod*(n%mod*2%mod+1)%mod*inv_6%mod;
}
void solve() {
int k;
cin >> k;
inv_6=ksm(6,mod-2);
int lo=1,hi=1e12;
int lim=1;
//求
auto check=[&](int mid)->bool{
return f(mid)<=k;
};
while(lo<=hi){
int mid=(lo+hi)/2;
if(check(mid)){
lim=mid;
lo=mid+1;
}else hi=mid-1;
}
// cout << lim << endl;
//找到了上限，對前面求和
int ans=0;
for(int l=1,r;l<=lim;l=r+1){
r=lim/(lim/l);
int m=lim/l;
ans=(ans+g(m)*((g(r)-g(l-1)+mod)%mod)%mod)%mod;
}
int r=k-f(lim);
ans=(ans+r*(lim%mod+1)%mod*(lim%mod+1)%mod)%mod;
cout << ans << endl;
}
/*
*/
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}H
最大化\(mex\oplus gcd\)，很經典的討論就是枚舉\(mex\)，我們只需要討論\(mex=0,1\)和\(mex>1\)的三種情況即可。
這道題有一個前置知識：
給定一個序列\(a\)，現在有不可重集合\(S\)以及\(a\)的子集\(A\)，那麼\(s=(\sum_{v\in A}{v})\in S\)，也就是説任選一個\(a\)的子集，其子集元素和\(sum\)是\(S\)中的元素，求\(a\)的子集合最大不能表示的數\(mex\)。
這個可以通過排序+貪心來解決，我們先對\(a\)進行排序，之後假設現在能夠表示\([0,x]\)，那麼可以討論現在枚舉的數\(a_i\)：
- 如果\(a_i>x+1\)，那麼\(mex=x+1\)；
- 否則可表示範圍為\([0,x+a_i]\)；
這個時間複雜度是\(O(n\log{n})\)的。
sol：
當\(mex=0\)時，\(ans=sum[r]-sum[l-1]\)。
當\(mex=1\)時，\(ans=(sum[r]-sum[l-1])\oplus 1\)。
當\(mex\geq 2\)時，\(gcd=1\)，我們只需要最大化\(mex\)就行，\(ans=mex\oplus 1\)。
最後答案肯定在三種情況中的一種，前面只需要維護前綴和以及0的個數即可。
對於第三個，因為有\(q\)個詢問，如果每次排序然後他貪心選擇的話，時間複雜度為\(O(qn\log{n})\)，顯然不行。那麼根據我們的前置知識，我們可以考慮使用數據結構來優化這個。
這裏有一個很神奇的結論，就是這裏\(mex\)的變化次數最多\(log{V}\)次，説是和斐波拉契數列的變化同階。所以使用可持久化線段樹的總複雜度為\(n\log^2{V}\)。
法一：可持久化線段樹
我們枚舉最大覆蓋值\(x\)，那麼每次查詢在\([l,r]\)中，值小於等於\(x+1\)的元素之和\(res\)，如果\(res=x\)，那麼最大覆蓋值無法再增大，否則\(x=res\)。肯定有的是\(res\geq x\)，所以當\(res=x\)時，我們退出。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 1e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
int root[N],tot;
int lc[N*32],rc[N*32],sum[N*32];
int a[N];
vector<int> v;
int n,m;
int build(int l,int r){
int id=++tot;
if(l==r) return id;
int m=l+r>>1;
lc[id]=build(l,m);
rc[id]=build(m+1,r);
return id;
}
int update(int prev,int l,int r,int pos,int add){
int id=++tot;
lc[id]=lc[prev];
rc[id]=rc[prev];
sum[id]=sum[prev]+add;
if(l==r) return id;
int m=l+r>>1;
if(pos<=m) lc[id]=update(lc[prev],l,m,pos,add);
else rc[id]=update(rc[prev],m+1,r,pos,add);
return id;
}
int query(int x,int y,int l,int r,int ql,int qr){
if(ql>qr) return 0;
if(ql<=l&&r<=qr) return sum[y]-sum[x];
int m=l+r>>1;
int res=0;
if(ql<=m) res+=query(lc[x],lc[y],l,m,ql,qr);
if(qr>m) res+=query(rc[x],rc[y],m+1,r,ql,qr);
return res;
}
void solve() {
cin >> n;
vector<int> sm(n+1),zero(n+1);
for(int i=1;i<=n;i++){
cin >> a[i];
v.push_back(a[i]);
sm[i]=sm[i-1]+a[i];
zero[i]=zero[i-1]+(a[i]==0?1:0);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
auto get_id=[&](int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
};
vector<int> id(n+1);
for(int i=1;i<=n;i++){
id[i]=get_id(a[i]);
}
int rsize=v.size();
root[0]=build(1,rsize);
for(int i=1;i<=n;i++){
root[i]=update(root[i-1],1,rsize,id[i],a[i]);
}
cin >> m;
while(m--){
int l,r;
cin >> l >> r;
if(zero[r]-zero[l-1]==0){
cout << sm[r]-sm[l-1] << endl;
continue;
}
int s=0;
while(1){
//查詢區間[l,r]小於等於need的值的和
int pos=upper_bound(v.begin(),v.end(),s+1)-v.begin();
int res=query(root[l-1],root[r],1,rsize,1,pos);
if(res==s) break;
s=res;
}
int mex=s+1;
int ans=sm[r]-sm[l-1];
if(mex>=1) ans=max(ans,1^(sm[r]-sm[l-1]));
if(mex>1) ans=max(ans,1^mex);
cout << ans << endl;
}
}
/*
*/
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}法二：離線莫隊+樹狀數組
我們對原問題進行離線，之後用樹狀數組維護前綴和，單次修改為\(\log{n}\)，單次查詢為\(\log{n}\)，那麼總時間複雜度應該為\(O(q\log{n}+n\sqrt{n}\log{n})\)，按道理後面那個完全會超呀。但是這道題就是可以過，這就是\(mex\)的神奇性質嘛。
但是還是非常極限了時間879ms，所以還是用可持久化線段樹好一點。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
struct Fenwick{
vector<int> sum;
int n;
Fenwick(int n){this->n=n;sum.resize(n+1);}
int lowbit(int x){return x&-x;}
void update(int pos,int k){for(int i=pos;i<=n;i+=lowbit(i)) sum[i]+=k;}
int query(int pos){int res=0;for(int i=pos;i;i-=lowbit(i)) res+=sum[i];return res;}
};
void solve() {
int n,m;
cin >> n;
vector<int> a(n+1),zero(n+1),sum(n+1);
for(int i=1;i<=n;i++){
cin >> a[i];
sum[i]=sum[i-1]+a[i];
zero[i]=zero[i-1]+(a[i]==0);
}
vector<int> b=a;
sort(b.begin(),b.end());
b.erase(unique(b.begin(),b.end()),b.end());
int rsize=b.size();
vector<int> id(n+1);
auto get_id=[&](int x){
return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
};
for(int i=1;i<=n;i++){
id[i]=get_id(a[i]);
}
cin >> m;
vector<array<int,3>> qu(m+1);
for(int i=1;i<=m;i++){
cin >> qu[i][0] >> qu[i][1];
qu[i][2]=i;
}
int B=sqrt(n)+1;
sort(qu.begin()+1,qu.end(),[&](array<int,3> x,array<int,3> y){
auto [l1,r1,id1]=x;
auto [l2,r2,id2]=y;
if((l1-1)/B!=(l2-1)/B) return (l1-1)/B<(l2-1)/B;
else return r1<r2;
});
Fenwick tr(rsize);
auto del=[&](int pos){
tr.update(id[pos],-a[pos]);
};
auto add=[&](int pos){
tr.update(id[pos],a[pos]);
};
auto get=[&](int l,int r){
int res=sum[r]-sum[l-1];
if(zero[r]-zero[l-1]==0){
return res;
}
int s=0;
while(1){
int pos=upper_bound(b.begin(),b.end(),s+1)-b.begin();
int sm=tr.query(pos);
if(sm==s) break;
s=sm;
}
int mex=s+1;
res=max(res,res^1);
if(mex>1) res=max(res,mex^1);
return res;
};
int cl=1,cr=0;
vector<int> ans(m+1);
for(int i=1;i<=m;i++){
auto[l,r,id]=qu[i];
while(l<cl) add(--cl);
while(cr<r) add(++cr);
while(l>cl) del(cl++);
while(r<cr) del(cr--);
ans[id]=get(l,r);
}
for(int i=1;i<=m;i++) cout << ans[i] << endl;
}
/*
*/
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}最後討論一下為什麼這裏求\(mex\)的次數最多\(\log{V}\)次。
看一個例子：
初始：[0,-1]
加入0：[0,0]
加入1：[0,1]
加入2：[0,3]
加入4：[0,7]
加入8：[0,15]很明顯了，如果當前覆蓋區間是\([0,x]\)，那麼下一次我們找的是\(x+1\)，那麼下一次覆蓋範圍為\([0,2\times x+1]\)，這個就能夠看出來了。
A
給定\(n\)個數排成一行，每5個數一組，將前面4個丟棄，保留第5個數，直到剩下的數小於4個，問最後剩下幾個數，分別是多少。
模擬一下可以知道，當前是\(n\)，那麼剩下的數為\(n/5+n\%5\)，我們記下每一輪的\(Q_j,r_j\)，這樣我們可以倒推：
如果當前剩下\(m\)個數，那麼對於\(idx\in[1,m]\)，可以分為下面兩種情況：
- 如果\(idx\le Q_j\)，那麼\(idx\)是整數分組中的，那麼前一輪的位置為\(5\times idx\)；
- 如果\(idx>Q_j\)，那麼\(idx\)是最後餘下的幾個數中的，那麼前一輪的位置為\(5\times Q_j+(idx-Q_j)\)；
所以我們直接按照這個模擬就行，時間複雜度為\(O(\log{n})\)。
#include <bits/stdc++.h>
using namespace std;
#define inf 1e18
#define endl '\n'
#define int long long
typedef long long ll;
typedef pair<int, int> pii;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 2e5 + 9, M = 2e5 + 9, mod = 1e9 + 7;
void solve() {
int n;
cin >> n;
vector<int> num,Q;
num.push_back(n);
while(num.back()>=4){
int v=num.back();
int q=v/5;
Q.push_back(q);
int r=v%5;
num.push_back(q+(r==4?0:r));
}
vector<int> ans;
for(int i=1;i<=num.back();i++){
int idx=i;
for(int j=Q.size()-1;j>=0;j--){
if(idx<=Q[j]) idx=idx*5;
else idx=Q[j]*5+(idx-Q[j]);
}
ans.push_back(idx);
}
cout << ans.size() << endl;
for(int i:ans) cout << i << " ";
cout << endl;
}
/*
*/
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
