SPOJ-DQUERY D-query
2022/5/23 23:21:35
本文主要是介绍SPOJ-DQUERY D-query,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
D-query
区间内,有多少个不同的数
莫队 模板题
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define endl '\n' const int maxn = 3e4 + 10; const int maxm = 2e5 + 10; int cnt[1000010], num[maxn]; int ans = 0, pos[maxn], last[maxm]; struct node { int l, r, id; node(){} node(int _l, int _r, int _id){l = _l; r = _r; id = _id;} }seg[maxm]; bool cmp(const node& a, const node& b) { return pos[a.l] ^ pos[b.l] ? pos[a.l] < pos[b.l] : (pos[a.l] & 1 ? a.r > b.r : a.r < b.r); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i=1; i<=n; i++) cin >> num[i]; int m; cin >> m; for(int i=0; i<m; i++) { int x, y; cin >> x >> y; seg[i] = node(x, y, i); } int t = sqrt(n); for(int i=0; i<n; i++) pos[i] = i / t; sort(seg, seg + m, cmp); int l = 1, r = 0; for(int i=0; i<m; i++) { while(r < seg[i].r) ans += (++cnt[num[++r]] == 1); while(l > seg[i].l) ans += (++cnt[num[--l]] == 1); while(r > seg[i].r) ans -= (--cnt[num[r--]] == 0); while(l < seg[i].l) ans -= (--cnt[num[l++]] == 0); last[seg[i].id] = ans; } for(int i=0; i<m; i++) cout << last[i] << endl; return 0; }
这篇关于SPOJ-DQUERY D-query的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24内网穿透资料入门教程
- 2024-12-24微服务资料入门指南
- 2024-12-24微信支付系统资料入门教程
- 2024-12-24微信支付资料详解:新手入门指南
- 2024-12-24Hbase资料:新手入门教程
- 2024-12-24Java部署资料
- 2024-12-24Java订单系统资料:新手入门教程
- 2024-12-24Java分布式资料入门教程
- 2024-12-24Java监控系统资料详解与入门教程
- 2024-12-24Java就业项目资料:新手入门必备教程