平面上有n個(gè)點(diǎn)，坐標(biāo)分別為(i, f[i])，有m個(gè)詢問，每一次詢問求出在(xl, yl, xr, yr)的區(qū)間當(dāng)中有多少個(gè)y坐標(biāo)不同的點(diǎn)。
數(shù)據(jù)范圍：1<=n, m<=1e5, 0<=f[i]<=1e5

莫隊(duì)+分塊（$O(1)$修改，$O(\sqrt{n})$查詢）

詢問可以離線出來，因?yàn)閤的坐標(biāo)是1到n互不相同的，所以將x當(dāng)做第一維來進(jìn)行莫隊(duì)的詢問排序。

接下來就是對(duì)y坐標(biāo)的處理，有兩個(gè)操作，一個(gè)是在f[i]的位置上進(jìn)行單點(diǎn)修改(+1或者-1)，另一個(gè)就是查詢(yl, yr)區(qū)間有多少個(gè)大于0的數(shù)。這樣單點(diǎn)修改區(qū)間查詢會(huì)容易想到線段樹或者樹狀數(shù)組的做法，但是這樣的話每一次修改就是$O(logn)$，總的復(fù)雜度會(huì)變成$O(n\sqrt{n}logn)$，感覺不是很能過。

后面看了sol，是用的分塊來處理y坐標(biāo)，也就是實(shí)現(xiàn)$O(1)$修改和$O(logn)$，每一次修改就是改這個(gè)位置的值以及所屬塊的值，所以是$O(1)$的，查詢是$O(\sqrt{n})$，不過查詢只會(huì)用到m次，所以總的復(fù)雜度就是$O((n+m)\sqrt{n})$

莫隊(duì)的排序函數(shù)之前寫裂了，l指針的比較應(yīng)該是所在塊的比較，希望下次不要再犯

const int N = 1e5 + 10; int a[N], belong[N], ans[N]; int res[N], sum[N];struct query {int xl, yl, xr, yr, num; }; query q[N];bool cmp(const query &a, const query &b) {if (belong[a.xl] ^ belong[b.xl])return a.xl < b.xl;if (belong[a.xl] & 1)return a.xr < b.xr;return a.xr > b.xr; }inline void add(int x) {if (!res[x]) sum[belong[x]] ++;res[x] ++; }inline void sub(int x) {res[x] --;if (!res[x]) sum[belong[x]] --; }int getAns(int l, int r) {int ans = 0;if (belong[l] == belong[r]){for (int i = l; i <= r; i ++)if (res[i] > 0)ans ++;return ans;}for (int i = l; belong[i] == belong[l]; i ++)ans += res[i] > 0;for (int i = r; belong[i] == belong[r]; i --)ans += res[i] > 0;for (int i = belong[l] + 1; i < belong[r]; i ++)ans += sum[i];return ans; }int main() {//freopen("1.in", "r", stdin);//freopen("out.txt", "w", stdout);int T = 1;T = read();int size = sqrt(N);for (int i = 0; i < N; i ++)belong[i] = i / size + 1;while (T --){int n = read(), m = read();for (int i = 1; i <= n; i ++)a[i] = read();for (int i = 1; i <= m; i ++){q[i].xl = read(); q[i].yl = read();q[i].xr = read(); q[i].yr = read();q[i].num = i;}sort (q + 1, q + m + 1, cmp);for (int i = 1; i <= n; i ++)res[i] = sum[i] = 0;int start = clock();int l = 1, r = 0;for (int i = 1; i <= m; i ++){while (l > q[i].xl) add(a[-- l]);while (r < q[i].xr) add(a[++ r]);while (l < q[i].xl) sub(a[l ++]);while (r > q[i].xr) sub(a[r --]);//printf ("%d\n", clock() - start);ans[q[i].num] = getAns(q[i].yl, q[i].yr);//printf ("%d\n", clock() - start);}for (int i = 1; i <= m; i ++)printf ("%d\n", ans[i]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的2021中超1 1010 zoto的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。