C53 可持久化线段树+离散化 P2464 [SDOI2008] 郁闷的小 J

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l+r)>>1)
int a[N], lsh[N * 2], cnt;
struct node{int opt, l, r, p, id;/*id:书的编码*/} q[N];
struct treenode{int ls, rs, siz/*区间数的个数*/;} tr[N*20];
int trlen, rt[N];

void pushup(int p){ tr[p].siz = tr[lc(p)].siz + tr[rc(p)].siz; }

void change(int &now, int l, int r, int p, int k)// 点修
{ 
    if (!now) now = ++trlen;
    if (l == r){ tr[now].siz += k; return; }
    if (p <= mid) change(lc(now), l, mid, p, k);
    else change(rc(now), mid + 1, r, p, k);
    pushup(now);
}
int query(int now, int l, int r, int x, int y)// 区查
{ 
    if (x <= l && r <= y) return tr[now].siz;
    int s = 0;
    if (x <= mid) s += query(lc(now), l, mid, x, y);
    if (y > mid) s += query(rc(now), mid + 1, r, x, y);
    return s;
}
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), lsh[i] = a[i]; // 保存书的编号
    cnt = n;
    for (int i = 1; i <= m; i++)// 保存操作
    { 
        char s[2]; scanf("%s", s);
        if (s[0] == 'C') q[i].opt = 0, scanf("%d%d", &q[i].p, &q[i].id);
        else q[i].opt = 1, scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].id);
        lsh[++cnt] = q[i].id; // 保存书的编号
    }
    sort(lsh + 1, lsh + cnt + 1);
    int ln = unique(lsh + 1, lsh + cnt + 1) - lsh - 1; // 去重
    trlen = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(lsh + 1, lsh + ln + 1, a[i]) - lsh; // 编码变成离散值
        change(rt[a[i]], 1, n, i, 1); // 按离散值建可持久化线段树
    }
    for (int i = 1; i <= m; i++)// 处理操作
    { 
        if (!q[i].opt)// 更换图书
        { 
            change(rt[a[q[i].p]], 1, n, q[i].p, -1);
            a[q[i].p] = lower_bound(lsh + 1, lsh + ln + 1, q[i].id) - lsh;
            change(rt[a[q[i].p]], 1, n, q[i].p, 1);
        }
        else // 查询某编码的书的个数
        {
            int id = lower_bound(lsh + 1, lsh + ln + 1, q[i].id) - lsh;
            printf("%d\n", query(rt[id], 1, n, q[i].l, q[i].r));
        }
    }
    return 0;
}

C53 可持久化线段树+离散化 P2464 [SDOI2008] 郁闷的小 J

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l+r)>>1)
int a[N], lsh[N * 2],cnt;
struct node{int opt, l, r,p, id;/id:书的编码/} q[N];
struct treenode{int ls,rs,siz/区间数的个数/;}tr[N*20];int trlen,rt[N];

void pushup(int p){ tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz;}

void change(int &now, int l, int r, int p, int k)// 点修 { if (!now)now=++trlen; if (l == r){tr[now].siz+= k;return;} if (p <= mid) change(lc(now), l, mid, p, k); else change(rc(now), mid + 1, r, p, k); pushup(now); } int query(int now, int l, int r, int x, int y)// 区查 { if(x<=l && r<=y)return tr[now].siz; int s=0; if(x<=mid)s+= query(lc(now), l, mid, x, y); if(y>mid) s+= query(rc(now), mid+1, r, x, y); return s; } int main() { int n,m;scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%d", &a[i]),lsh[i] = a[i]; // 保存书的编号 cnt=n; for (int i = 1; i <= m; i++)// 保存操作 { char s[2];scanf("%s", s); if(s[0]=='C') q[i].opt = 0, scanf("%d%d", &q[i].p, &q[i].id); else q[i].opt = 1, scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].id); lsh[++cnt] = q[i].id; // 保存书的编号 } sort(lsh+1, lsh+cnt+1); int ln = unique(lsh+1, lsh+cnt+1) - lsh - 1; // 去重 trlen=0; for (int i = 1; i <= n; i++) { a[i] = lower_bound(lsh+1,lsh+ln+1,a[i]) - lsh; // 编码变成离散值 change(rt[a[i]], 1, n, i, 1); // 按离散值建可持久化线段树 } for (int i = 1; i <= m; i++)// 处理操作 { if (!q[i].opt)// 更换图书 { change(rt[a[q[i].p]], 1, n, q[i].p, -1); a[q[i].p] = lower_bound(lsh+1,lsh+ln+1,q[i].id) - lsh; change(rt[a[q[i].p]], 1, n, q[i].p, 1); } else // 查询某编码的书的个数 { int id = lower_bound(lsh + 1, lsh + ln + 1, q[i].id) - lsh; printf("%d\n", query(rt[id], 1, n, q[i].l, q[i].r)); } } return 0; }</pre>