[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