CodeChef - QCHEF 分块-白红宇

CodeChef - QCHEF 分块

阅读量：7090 次

发布时间：2019-06-28

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

题目链接：http://vjudge.net/problem/174774/origin

题意：给定一个长度为n的序列a[],序列的值不大于m，现在有k个询问，每个询问给定(l,r).让你求出max{|x − y| : Li ≤ x, y ≤ Ri and Ax = Ay}。即区间[L,R]中值相同时，位置差的最大值

思路：分块，因为不带修改，所以我们就可以做预处理。求出last,first,Ans。 last[i][j]:值i在第j块最后出现的位置。first[i][j]:值i在第j块最早出现的位置。Ans[i][j]:第i块到第j块的值相同的最大位置差。

#define _CRT_SECURE_NO_DEPRECATE#include
     
        #include
      
         #include
       
        #include
        
           #include
         
            #include
          
            #include
           
            #include
            
             #include
             
              #include
              using namespace std;typedef long long int LL;const int MAXN = 100000 + 10;int belong[MAXN], block, num, L[MAXN], R[MAXN];int n, m, q;int a[MAXN], last[MAXN][500], first[MAXN][500], Ans[500][500];int tim[MAXN], times, Pos[MAXN];int cal(int st, int ed){ int ans = 0; for (int i = L[st]; i <= R[st]; i++){ ans = max(ans, last[a[i]][ed] - i); } return ans;}void build(){ block = (int)sqrt(n + 0.5); num = n / block; if (n%block){ num++; } for (int i = 1; i <= num; i++){ L[i] = (i - 1)*block + 1; R[i] = i*block; } R[num] = n; for (int i = 1; i <= n; i++){ belong[i] = ((i - 1) / block) + 1; } memset(last, 0, sizeof(last)); memset(first, 0, sizeof(first)); memset(Ans, 0, sizeof(Ans)); times = 0; for (int i = 1; i <= n; i++){ last[a[i]][belong[i]] = i; } for (int i = n; i>0; i--){ first[a[i]][belong[i]] = i; } for (int i = 1; i <= m; i++){ for (int j = 1; j <= num; j++){ if (!last[i][j]){ last[i][j] = last[i][j - 1]; } } for (int j = num; j; j--){ if (!first[i][j]){ first[i][j] = first[i][j + 1]; } } } for (int i = num; i; i--){ for (int j = i; j <= num; j++){ Ans[i][j] = max(max(Ans[i + 1][j], Ans[i][j - 1]), cal(i, j)); } }}int query(int st, int ed){ int ans = 0; times++; if (belong[st] == belong[ed]){ for (int i = st; i <= ed; i++){ if (tim[a[i]] != times){ Pos[a[i]] = i; tim[a[i]] = times; } else{ ans = max(ans, i - Pos[a[i]]); } } return ans; } for (int i = st; i <= R[belong[st]]; i++){ if (tim[a[i]] != times){ Pos[a[i]] = i; tim[a[i]] = times; } else{ ans = max(ans, i - Pos[a[i]]); } ans = max(ans, last[a[i]][belong[ed] - 1] - i); } ans = max(ans, Ans[belong[st] + 1][belong[ed] - 1]); for (int i = L[belong[ed]]; i <= ed; i++){ if (tim[a[i]] != times){ Pos[a[i]] = i; tim[a[i]] = times; } else{ ans = max(ans, i - Pos[a[i]]); } ans = max(ans, i - first[a[i]][belong[st] + 1]); } return ans;}int main(){ //#ifdef kirito // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); //#endif // int start = clock(); while (~scanf("%d%d%d", &n, &m, &q)){ for (int i = 1; i <= n; i++){ scanf("%d", &a[i]); } build(); int st, ed; for (int i = 1; i <= q; i++){ scanf("%d%d", &st, &ed); printf("%d\n", query(st, ed)); } } //#ifdef LOCAL_TIME // cout << "[Finished in " << clock() - start << " ms]" << endl; //#endif return 0;}

转载于:https://www.cnblogs.com/kirito520/p/5952353.html

你可能感兴趣的文章