JZOJ 4747 被粉碎的线段树

发表于 | 分类于 |

根据套路，这个找找规律就好了……
得到规律：答案为 \(2L - C\)，其中 \(L\) 表示区间长度，\(C\) 表示被询问覆盖的结点个数。

于是就是一个二维偏序。
可以用排序忽略第一维之间的影响之后用权值线段树或权值树状数组维护第二维。
但是由于值域都是 \([1,n]\) 的，所以我选择了用主席树来维护。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5;
const int M = 1e5;
int n,m;
struct node
{
    int cnt;
    int ls,rs;
} seg[(N << 7) + 10];
int rt[N + 5];
vector<int> pos[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],p = tot,seg[p].cnt += k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    if(x <= mid)
        insert(x,k,seg[p].ls,tl,mid);
    else
        insert(x,k,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int tl,int tr)
{
    if(!p || (l <= tl && tr <= r))
        return seg[p].cnt;
    int mid = tl + tr >> 1;
    int ret = 0;
    if(l <= mid)
        ret += query(l,r,seg[p].ls,tl,mid);
    if(r > mid)
        ret += query(l,r,seg[p].rs,mid + 1,tr);
    return ret;
}
void dfs(int l,int r)
{
    pos[l].push_back(r);
    if(l == r)
        return ;
    int mid;
    scanf("%d",&mid);
    dfs(l,mid),dfs(mid + 1,r);
}
int main()
{
    scanf("%d%d",&n,&m);
    dfs(1,n);
    for(register int i = 1;i <= n;++i)
    {
        rt[i] = rt[i - 1];
        for(register int j = 0;j < pos[i].size();++j)
            insert(pos[i][j],1,rt[i],1,n);
    }
    int l,r;
    while(m--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",2 * (r - l + 1) - query(1,r,rt[n],1,n) + query(1,r,rt[l - 1],1,n));
    }
}