[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)...