[TIOJ] 1726. Dice Wars

題目連結:http://tioj.infor.org/problems/1726
為什麼$O((N+Q)\sqrt{N})$跑得比$O((N+Q)\sqrt{N}log(N))$還要慢啊，我居然是倒數的，明明上面的人複雜度都慘的（？
總之我的想法是分塊，然後對每塊都用$O(N^2)$的方式算完每塊內的答案，接著如果答案是跨多個塊的話，則我們只要掃過每一塊，並記錄當前遇到最後面的a跟b出現在哪，然後再看看現在看到這塊的a跟b最前面出現在哪就好，完成後更新a,b的最後位置，再去檢查下一塊。
易知當塊大小為k時，複雜度為$O(Nk+\frac{NQ}{k})$故取$k=\sqrt{N}$時最佳。

---

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_map>
using namespace std;
const int N = 60025 + 5;
const int SQRT_N = 245;
const int INF = 1<<30;

vector<pair<int,int>> que;
unordered_map<int,int> ans[N], fi[SQRT_N], se[SQRT_N];
int arr[N];

int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int n, q; cin >> n >> q;
   for(int i=0;i<n;i++) cin >> arr[i];
   n = (n+SQRT_N-1)/SQRT_N*SQRT_N;
   for(int i=0;i<q;i++){
      int x, y; cin >> x >> y;
      if(x > y) swap(x,y);
      ans[x][y] = INF;
      que.emplace_back(x, y);
   }
   for(int i=0;i<n;i+=SQRT_N){
      for(int j=i;j<i+SQRT_N;j++){
         for(int k=j;k<i+SQRT_N;k++){
            int a = arr[j], b = arr[k];
            if(a > b) swap(a, b);
            if(ans[a].find(b)!=ans[a].end())
               ans[a][b] = min(ans[a][b], k-j);
         }
      }
      for(int j=i;j<i+SQRT_N;j++) se[i/SQRT_N][arr[j]] = j;
      for(int j=i+SQRT_N-1;j>=i;j--) fi[i/SQRT_N][arr[j]] = j;
   }
   for(auto qq: que) {
      int a, b; tie(a, b) = qq;
      int ret = ans[a][b];
      int laA = -1, laB = -1;
      for(int i=0;i<n/SQRT_N;i++){
         if(laA != -1 and fi[i].find(b)!=fi[i].end())
            ret = min(ret, fi[i][b]-laA);
         if(laB != -1 and fi[i].find(a)!=fi[i].end())
            ret = min(ret, fi[i][a]-laB);
         if(se[i].find(a)!=se[i].end()) laA = se[i][a];
         if(se[i].find(b)!=se[i].end()) laB = se[i][b];
      }
      cout << (ret==INF?-1:ret) << '\n';
   }
   return 0;
}