HDU 6534 Chika and Friendly Pairs (树状数组离散化莫队)-白红宇

HDU 6534 Chika and Friendly Pairs (树状数组离散化莫队)

阅读量：5050 次

发布时间：2019-06-12

本文共 2291 字，大约阅读时间需要 7 分钟。

树状数组离散化莫队

求[L,R]内有多少对(i, j)满足|a[i] - a[j]| <= K，我们转换为求[a[i] - k - 1, a[i] + k]的个数

离散化处理a[i], a[i] - k, a[i] + k的下标(二分处理)

然后莫队查询，用树状数组维护这些数，实现区间查询，区间修改

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #define rep(i, s, e) for(int i = s; i < e; ++i)#define P pair
                
                 #define INF 0x3f3f3f3fusing namespace std;typedef long long ll;static const int N = 35;static const int MAX_N = 27005;static const ll Mod = 1e9 + 7;int a[MAX_N], b[MAX_N * 3], c[MAX_N * 3], suml[MAX_N], sumr[MAX_N], rev[MAX_N];int maxv;struct Query{ int l, r, pos, id; bool operator < (const Query &rhs)const{ return (pos ^ rhs.pos) ? l < rhs.l : (pos & 1) ? r < rhs.r : r > rhs.r; }}q[MAX_N];int lowbit(int x){ return x & (-x);}void update(int p, int v){ for(int i = p; i <= maxv; i += lowbit(i)) c[i] += v;}int query(int p){ int rt = 0; for(int i = p; i; i -= lowbit(i)) rt += c[i]; return rt;}void solve(){// freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout); int n, m, k; scanf("%d%d%d", &n, &m, &k); maxv = n * 3; int cnt = 0; for(int i = 1; i <= n; ++i){ scanf("%d", &a[i]); b[++cnt] = a[i] - k; b[++cnt] = a[i]; b[++cnt] = a[i] + k; } int block = (int)sqrt(n); for(int i = 1; i <= m; ++i){ scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; q[i].pos = (q[i].l - 1) / block + 1; } sort(b + 1, b + cnt + 1); int cur = unique(b + 1, b + cnt + 1) - b - 1; for(int i = 1; i <= n; ++i){ suml[i] = lower_bound(b + 1, b + cur + 1, a[i] - k) - b; sumr[i] = lower_bound(b + 1, b + cur + 1, a[i] + k) - b; a[i] = lower_bound(b + 1, b + cur + 1, a[i]) - b; } sort(q + 1, q + m + 1); int l = 1, r = 0; int ans = 0; for(int i = 1; i <= m; ++i){ while(l < q[i].l){ update(a[l], -1); ans -= query(sumr[l]) - query(suml[l] - 1); ++l; } while(l > q[i].l){ --l; ans += query(sumr[l]) - query(suml[l] - 1); update(a[l], 1); } while(r > q[i].r){ update(a[r], -1); ans -= query(sumr[r]) - query(suml[r] - 1); --r; } while(r < q[i].r){ ++r; ans += query(sumr[r]) - query(suml[r] - 1); update(a[r], 1); } rev[q[i].id] = ans; } for(int i = 1; i <= m; ++i) printf("%d\n", rev[i]);}int main() { solve(); return 0;}