洛谷P1972 [SDOI2009]HH的項鍊
标簽
- 基礎莫隊
- 卡常
- 線段樹離線
前言
- 我的csdn和部落格園是同步的，歡迎來訪danzh-部落格園~
- 這才是最裸的莫隊惹。然而資料加強了，莫隊需要吸氧+卡常才能過，這篇文章簡單講講卡常，主要講線段樹
簡明題意
- 給一個序列，每次詢問你區間[L,R]中有多少種不同的數字
思路
- 這才是最裸的莫隊惹。然而資料加強了，莫隊需要吸氧+卡常才能過，然後卡常的相關操作寫到總結裡吧~
-
然後還有一種用權值線段樹維護的不那麼暴力的方法。（很巧妙的鴨）
--------------------------------------------------------分鴿線--------------------------------------------------------
- 首先，我們看這樣一組樣例：
1 , 2 , 4 , 5 , 2 , 4 , 2 1,2,4,5,2,4,2 1,2,4,5,2,4,2
- 我們把相同的數中的最後一個置為1
1 , 2 , 4 , 5 , 2 , 4 , 2 1,2,4,5,2,4,2 1,2,4,5,2,4,2
1 , 0 , 0 , 1 , 0 , 1 , 1 1,0,0,1,0,1,1 1,0,0,1,0,1,1
- 因為每個數隻會産生一個1，是以現在要求區間[L,R]中不同的數的個數，就直接統計1的個數就行了。
- 仔細想想，上面直接統計1的個數是不對的。比如查詢[3,3]，顯然按上面的方法查到的是0，而實際卻是1。為什麼？實際上，上面的統計方法是對的，隻是，隻有當查詢的右端點是最後一個數，也就是右端點r=7時，才是對的（仔細想想為什麼），而左端點可以是任意的。
- 顯然當右端點固定是時，上面的東西是可以用線段樹維護的，維護一下區間的和就可以了。
- 但是每次詢問右端點都不一樣。怎麼辦呢？可以借助主席樹的思想了，每移動一次右端點，就更新一下目前的線段樹，保證線段樹維護的是對于目前r的區間和。
- 是以說應該離線，把詢問按照右端點排序，每次右端點增大，就先更新一下線段樹，然後再查詢。
- 最後說說更新線段樹，比如所要更新i=5。那麼應該把01序列中的第5個改為1，然後再把第5個數2的前面的一個2，線上段樹中将他改為0.是以說我們需要預處理每個數a[i]的前一個和他相同的數的下表，就這樣這題就能AC
注意事項
- 無
總結
莫隊部分
- 快讀，快寫
inline int read()
{
int ans = 0;
char r = getchar(); bool neg = false;
while (r<'0' || r>'9') { if (r == '-')neg = true; r = getchar(); }
while (r >= '0'&&r <= '9') { ans = ans * 10 + r - '0'; r = getchar(); }
return (neg) ? -ans : ans;
}
void write(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}//write不帶換行符，需要自己putchar('\n')
- 奇偶性排序
bool operator < (const Query& a)const
{
return pos[l] ^ pos[a.l] ? pos[l] < pos[a.l] : pos[l] & 1 ? r<a.r : r>a.r;
}
- 分塊的大小
線段樹部分
- 要随時能想到這種線段樹離線的方法~
AC代碼
莫隊
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
int ans = 0;
char r = getchar(); bool neg = false;
while (r<'0' || r>'9') { if (r == '-')neg = true; r = getchar(); }
while (r >= '0'&&r <= '9') { ans = ans * 10 + r - '0'; r = getchar(); }
return (neg) ? -ans : ans;
}
void write(int x) {
if (x < 0) { putchar('-'); x = -x; }
if (x > 9)write(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 1e6 + 10;
int pos[maxn];
struct Query
{
int l, r, id;
bool operator < (const Query& a)const
{
return pos[l] ^ pos[a.l] ? pos[l] < pos[a.l] : pos[l] & 1 ? r<a.r : r>a.r;
}
};
Query query[maxn];
int n, q, a[maxn];
int ans, cnt[maxn];
int ans0[maxn];
void solve()
{
scanf("%d", &n);
int len = n / sqrt(n * 2 / 3);
for (int i = 1; i <= n; i++)
a[i] = read(), pos[i] = (i - 1) / len + 1;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
query[i].l = read(), query[i].r = read(), query[i].id = i;
sort(query + 1, query + 1 + q);
int l = 1, r = 0;
for (int i = 1; i <= q; i++)
{
int L = query[i].l, R = query[i].r;
while (l < L) if (cnt[a[l++]]-- == 1) ans--;
while (l > L)if (cnt[a[--l]]++ == 0) ans++;
while (r < R) if (cnt[a[++r]]++ == 0) ans++;
while (r > R) if (cnt[a[r--]]-- == 1) ans--;
ans0[query[i].id] = ans;
}
for (int i = 1; i <= q; i++)
write(ans0[i]), putchar('\n');
}
int main()
{
//freopen("Testin.txt", "r", stdin);
solve();
return 0;
}
線段樹
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 10;
struct Query
{
int l, r, id;
bool operator < (const Query& a)const
{
return r < a.r;
}
};Query query[maxn];
struct Node
{
int l, r, sum;
}; Node tree[maxn * 4];
void build(int o, int l, int r)
{
tree[o].l = l, tree[o].r = r;
if (l == r)
return;
int mid = (l + r) / 2;
build(o * 2, l, mid);
build(o * 2 + 1, mid + 1, r);
}
void change(int o, int x, int type)
{
if (tree[o].l == tree[o].r)
{
tree[o].sum = type;
return;
}
int mid = (tree[o].l + tree[o].r) / 2;
if (x <= mid)
change(o * 2, x, type);
else
change(o * 2 + 1, x, type);
tree[o].sum = tree[o * 2].sum + tree[o * 2 + 1].sum;
}
int ask(int o, int l, int r)
{
if (tree[o].l == l && tree[o].r == r)
return tree[o].sum;
int mid = (tree[o].l + tree[o].r) / 2;
if (r <= mid)
return ask(o * 2, l, r);
else if (l > mid)
return ask(o * 2 + 1, l, r);
return ask(o * 2, l, mid) + ask(o * 2 + 1, mid + 1, r);
}
int n, q, a[maxn];
int ans0[maxn];
int las[maxn], pos[maxn];
void solve()
{
build(1, 1, maxn - 10);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), las[i] = pos[a[i]], pos[a[i]] = i;
scanf("%d", &q);
for (int i = 1; i <= q; i++)
scanf("%d%d", &query[i].l, &query[i].r), query[i].id = i;
sort(query + 1, query + 1 + q);
int las_r = 1;
for (int i = 1; i <= q; i++)
{
int l = query[i].l, r = query[i].r;
for (int i = las_r; i <= r; i++)
{
if (las[i] != 0)
change(1, las[i], 0);
change(1, i, 1);
}
ans0[query[i].id] = ask(1, l, r);
las_r = r + 1;
}
for (int i = 1; i <= q; i++)
printf("%d\n", ans0[i]);
}
int main()
{
freopen("Testin.txt", "r", stdin);
solve();
return 0;
}