Maximum Multiple:
这题一开始一直想着化简后二分三分，但是不太对。
考虑到因子限制，对原式变形可得$1 = frac{1}{a} + frac{1}{b} + frac{1}{c}$
然后这个式子只有三种解：
2 4 4
3 3 3
2 3 6
然后取最大的即可。（简单题不应该想的太复杂）
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e6+5; const int M = 1e6+5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read() { LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();} return x * f; } } using namespace FASTIO; vector<int> vec; int main() { int ca;ca = read(); while(ca--) { int n;n = read(); if(n < 3) printf("-1 "); else { LL ma = -1; if(n % 4 == 0) ma = max(ma,1LL * (n / 2) * (n / 4) * (n / 4)); if(n % 3 == 0) ma = max(ma,1LL * (n / 3) * (n / 3) * (n / 3)); if(n % 6 == 0) ma = max(ma,1LL * (n / 2) * (n / 3) * (n / 6)); printf("%lld ",ma); } } system("pause"); return 0; }
Distinct Values:
思路是对了，不过有个细节问题。
首先，对于询问离线后贪心排序，先左边界降序，然后右边界降序。
然后线段树维护能插入的数。
这里犯了个错误，就是左边界才是第一排序贪心位置，而我维护的时候用了右边界的，这样不能保证所有合并后遍历位置为n，所以TLE了。
其实要按L来走，这样的话就能保证复杂度了。
还有一个主要的卡复杂度的地方就是右边界要保证一直维护，因为可能很前面的右边界就已经到了n，这样会走重复的路，导致TLE。
核心优化就是不要走重复的路。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e5+5; const int M = 1e6+5; const LL Mod = 1e9 + 7; #define pi acos(-1) #define INF 1e18 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read() { LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();} return x * f; } } using namespace FASTIO; struct Query{ int L,r; bool operator < (const Query a)const{ if(L == a.L) return r < a.r; else return L < a.L; } }p[N]; int ans[N]; struct Node{int L,r,sum;}node[N << 2]; void Pushup(int idx) { node[idx].sum = node[idx << 1].sum + node[idx << 1 | 1].sum; } void build(int L,int r,int idx) { node[idx].L = L,node[idx].r = r,node[idx].sum = 0; if(L == r){node[idx].sum = 1;return ;} int mid = (L + r) >> 1; build(L,mid,idx << 1); build(mid + 1,r,idx << 1 | 1); Pushup(idx); } void update(int x,int idx,int id) { if(node[idx].L == node[idx].r) { if(id == 1) node[idx].sum = 1; else node[idx].sum = 0; return ; } int mid = (node[idx].L + node[idx].r) >> 1; if(mid >= x) update(x,idx << 1,id); else update(x,idx << 1 | 1,id); Pushup(idx); } int query(int L,int r,int idx) { if(node[idx].L == node[idx].r) return node[idx].L; int mid = (node[idx].L + node[idx].r) >> 1; if(mid >= L && node[idx << 1].sum > 0) return query(L,r,idx << 1); else return query(L,r,idx << 1 | 1); } int main() { int ca;ca = read(); while(ca--) { int n,m;n = read(),m = read(); for(int i = 1;i <= n;++i) ans[i] = 0; int mx = -1; for(int i = 1;i <= m;++i) p[i].L = read(),p[i].r = read(),mx = max(mx,p[i].r); sort(p + 1,p + m + 1); build(1,n,1); int r = p[0].L; for(int i = 1;i <= m;++i) { if(i > 1) for(int j = p[i - 1].L;j < p[i].L;++j) update(ans[j],1,1); for(int j = max(r,p[i].L);j <= p[i].r;++j) { ans[j] = query(1,n,1); update(ans[j],1,0); } r = max(r,p[i].r + 1); } for(int i = 1;i <= n;++i) if(ans[i] == 0) ans[i] = 1; for(int i = 1;i <= n;++i) printf("%d%c",ans[i],i == n ? ' ' : ' '); } //system("pause"); return 0; }