query 2019徐州网络赛（树状数组）

悠悠 2023-08-17 17:04 127阅读 0赞

# query #

\\\[ Time Limit: 2000 ms \\quad Memory Limit: 262144 kB \\\]

## 题意 ##

补题才发现比赛的时候读了一个假题意....  
给出长度为 \\(n\\) 的排列，在给出 \\(m\\) 次询问，每次询问有一对 \\(l、r\\)，问满足 \\(min(ai, aj) = gcd(ai, aj)\\) 的 \\(pair(i, j)\\) 对数。

## 思路 ##

考虑离线做  
先把每个数出现的位置记录下来，然后预处理出所有的 \\(pair\\)。  
对于一个数字 \\(x\\)，其满足条件的另一个数有 \\(\\sum\_\{k=2\}^\{\\lfloor\\frac\{n\}\{x\}\\rfloor\}kx\\)，那么就可以预处理每一个 \\(x\\)，找出所有的 \\(kx\\)，记录 \\(x\\) 和 \\(kx\\) 的位置，就是一对 \\(pair\\)。  
保存一对 \\(pair\\) 时，将信息保存在较右的位置上。  
那么我们就可以每次更新一个位置，更新时候将以这个位置为右端点的所有左端点释放出来，表示存在一个答案。  
然后边更新边查询，当某个询问的右端点正好是我现在刚刚更新完的点时，由于已经更新出来的所有 \\(pair\\) 的右端点都在询问的 \\(r\\) 左侧，那么只要保证这些 \\(pair\\) 的左端点都在询问的 \\(l\\) 右侧就可以，那么我就可以更新 \\(pair\\) 的时候，更新在左侧，然后用树状数组来查询区间内的和。

/*************************************************************** > File Name : a.cpp > Author : Jiaaaaaaaqi > Created Time : Mon 09 Sep 2019 11:49:25 PM CST ***************************************************************/ #include <map> #include <set> #include <list> #include <ctime> #include <cmath> #include <stack> #include <queue> #include <cfloat> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <unordered_map> #define lowbit(x) x & (-x) #define mes(a, b) memset(a, b, sizeof a) #define fi first #define se second #define pb push_back #define pii pair<int, int> typedef unsigned long long int ull; typedef long long int ll; const int maxn = 1e5 + 10; const int maxm = 1e5 + 10; const ll mod = 1e9 + 7; const ll INF = 1e18 + 100; const int inf = 0x3f3f3f3f; const double pi = acos(-1.0); const double eps = 1e-8; using namespace std; int n, m; int cas, tol, T; struct Node { int l, r, id; bool operator < (Node a) const { return r<a.r; } } node[maxn]; int a[maxn], p[maxn]; int ans[maxn]; vector<int> vv[maxn]; int sum[maxn]; void update(int p) { for(int i=p; i<=n; i+=lowbit(i)) { sum[i] ++; } } int query(int p) { int ans = 0; for(int i=p; i>=1; i-=lowbit(i)) { ans += sum[i]; } return ans; } int main() { // freopen("in", "r", stdin); scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) { scanf("%d", &a[i]); p[a[i]] = i; vv[i].clear(); } for(int i=1; i<=n; i++) { for(int j=i+i; j<=n; j+=i) { vv[max(p[i], p[j])].pb(min(p[i], p[j])); } } for(int i=1; i<=m; i++) { scanf("%d%d", &node[i].l, &node[i].r); node[i].id = i; } sort(node+1, node+1+m); int ask = 1; for(int i=1; i<=n; i++) { if(ask > m) break; for(auto j : vv[i]) update(j); while(ask<=m && node[ask].r == i) { ans[node[ask].id] = query(i) - query(node[ask].l-1); ask++; } } for(int i=1; i<=m; i++) { printf("%d\n", ans[i]); } return 0; }

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/11495145.html