http://acm.hdu.edu.cn/showproblem.php?pid=6534

題意：給你一個序列，多次詢問，每次讓你回答一個區間中差的絕對值不超過一個給定常數K的元素對數。

題解：對序列中的所有元素以及這些元素+K，-K后的值進行離散化。 然后使用莫隊算法，在莫隊算法的端點移動過程中，新加入一個元素x的過程中，將其插入樹狀數組，查詢[x-K,x+K]范圍的元素數即可。刪除一個元素的過程與其類似。

C++版本一

題解：莫隊+樹狀數組+離散化

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l[N],r[N],u,v; int ans[N],cnt,flag,temp,tot; int a[N],b[N],c[N],be[N]; char str; struct node{int l,r,id;bool operator <(const node &S)const{return (be[l] ^ be[S.l]) ? be[l] < be[S.l] : ((be[l] & 1) ? r < S.r : r > S.r);} }e[N]; int tree[N]; void add(int x,int C){for(int i=x;i<=tot;i+=i&-i){tree[i]+=C;} } int sum(int x){int res=0;for(int i=x;i>0;i-=i&-i){res+=tree[i];}return res; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){scanf("%d%d%d",&n,&m,&k);int sz = sqrt(n);int bnum = ceil((double)n / sz);for (int i = 1; i <= bnum; i++){for (int j = (i - 1) * sz + 1; j <= i * sz; j++)be[j] = i;}for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+n+1);c[1]=b[1];tot=1;for(int i=2;i<=n;i++)if(b[i-1]!=b[i])c[++tot]=b[i];for(int i=1;i<=m;i++){scanf("%d%d",&e[i].l,&e[i].r);e[i].id=i;}sort(e+1,e+m+1);for (int i = 1; i <= n; i++){l[i] = lower_bound(c+1,c+tot+1, a[i] - k) - c ;r[i] = upper_bound(c+1,c+tot+1, a[i] + k) - c - 1;a[i] = lower_bound(c+1,c+tot+1, a[i]) - c ;}int L = 1, R = 0, temp = 0;for (int i = 1; i <= m; i++){int ql = e[i].l, qr = e[i].r;while(L < ql){add(a[L], -1);temp -= sum(r[L]) - sum(l[L] - 1);L++;}while(L > ql){L--;temp += sum(r[L]) - sum(l[L] - 1);add(a[L], 1);}while(R < qr){R++;temp += sum(r[R]) - sum(l[R] - 1);add(a[R], 1);}while(R > qr){add(a[R], -1);temp -= sum(r[R]) - sum(l[R] - 1);R--;}ans[e[i].id] = temp;//cout<<L<<" "<<R<<endl;//cout<<temp<<endl;}for(int i=1;i<=m;i++){cout<<ans[i]<<endl;}//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }/**//* 5 5 3 2 5 7 1 3 6 6 1 3 2 4 1 5 2 3 */

總結

以上是生活随笔為你收集整理的Chika and Friendly Pairs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。