题目：传送门
题意
给你 n,m,l,r；你需要找到 (x1, x2, y1, y2) 这样的四元组，满足：
1 <= x1 < x2 <= n;
1 <= y2 < y1 <= m;
x1*y1 = x2*y2;
l <= x1*y1 <= r;
对于每个x1=1,2,....n; 输出任意一个满足条件的四元组，若不存在这样的四元组，输出 -1；
1<=n,m<=2e5; 1 <= l <= r <= n * m;
思路
对于 x1*y1 = x2*y2; 我们假设 x1 < x2,可以证明总是存在一对(a,b) (a | x1, b | y1, a < b) 使得 x2 = x1 / a * b; y2 = y1 / b * a;
我可以枚举 x1，然后知道了 x1 就确定了 y1 的取值范围，由于 a 是 x1 的因子，我们可以枚举 a，通过 a 去 确定 b，若 b 确定了，则所有数都确定了。
我们可以在 o(nlogn) 的时间内算出所有的 (x1, a)；
然后我们枚举 x1，通过 x1 可以确定 y1 的取值范围，是一段区间，并且随着 x1 的增大，这个区间一直在收缩；对于这个区间的维护，我们可以用两个指针，指向这段区间的左端和右端；然后随着 x1 的变化，动态的维护这段区间即可。
我们可以用 set 存 y1 的所有所有可能取值的所有因子，这样， set里面存的数就是 b 的可能取值。
对于每个 a，若 x1 / a * b <= n；则存在答案；所以，若第一个大于a的b满足 x1 / a * b <= n；就更新 x1 的答案；
我们可以通过 upper_bound 找到 set 中第一个大于 a 的 b；
#include <bits/stdc++.h> #define LL long long #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k;i >= j; i--) #define pb push_back #define make make_pair #define fir first #define sec second using namespace std; const int N = 1e6 + 5; LL n, m; LL l, r; vector < LL > Y[N]; pair < LL, LL > ans1[N], ans2[N]; set < LL > Q; vector < LL > id(N, 0); vector < LL > cnt(N, 0); void solve() { scanf("%lld %lld %lld %lld", &n, &m, &l, &r); rep(i, 1, 200000) { /// 枚举所有 (x1, a) for(LL j = i; j <= 200000; j += i) { Y[j].pb(i); } } LL nowl = m + 1; /// y1的可能取值区间的左端点； LL nowr = m; /// y1 的可能取值区间的右端点 rep(x1, 1, n) { /// 枚举 x1 LL LY = (l + x1 - 1) / x1; /// 确定当前的 y1 可能取值区间的左端点； LL RY = r / x1; /// 确定当期 y1 的可能取值区间的右端点 while(nowl > LY) { /// 移动左指针，维护 y1 的可能取值区间 nowl--; for(int v : Y[nowl]) { if(cnt[v] == 0) Q.insert(v); cnt[v]++; id[v] = nowl; } } while(nowr > RY) { /// 移动右指针 for(int v : Y[nowr]) { cnt[v]--; if(cnt[v] == 0) Q.erase(v); } nowr--; } for(auto a : Y[x1]) { /// 枚举 a auto v = Q.upper_bound(a); if(v == Q.end()) continue; int b = *v; if(x1 / a * b <= n) { /// 满足条件，更新答案 int y1 = id[b]; ans1[x1] = make(x1, y1); ans2[x1] = make(x1 / a * b, y1 / b * a); } } } rep(i, 1, n) { if(ans1[i].fir != 0) { printf("%lld %lld %lld %lld ", ans1[i].fir, ans1[i].sec, ans2[i].fir, ans2[i].sec); } else puts("-1"); } } int main() { // int _; scanf("%d", &_); // while(_--) solve(); solve(); return 0; }