C35 线段树+排序（离线） P1972 [SDOI2009] HH的项链

C35 线段树+排序（离线） P1972 [SDOI2009] HH的项链
cpp #include <bits/stdc++.h> // 线段树+排序 using namespace std; #define lc(p) (p<<1) #define rc(p) (p<<1|1) const int N = 1e6 + 10; struct tree{ int l, r, s;} tr[N * 4]; struct node{ int l, r, id;} q[N]; // 查询 vector<int> v[N]; // 右端点相同的查询 int a[N], last[N], ans[N]; void pushup(int p) { tr[p].s = tr[lc(p)].s + tr[rc(p)].s; } void bt(int p, int l, int r) // 建树 { tr[p] = {l, r, 0}; if(l==r) {tr[p].s=1;return;} int mid=(l+r)>>1; bt(lc(p), l, mid); bt(rc(p), mid + 1, r); pushup(p); } void change(int p, int x) // 点修 { if(tr[p].l==tr[p].r){tr[p].s= 0;return;} int mid=(tr[p].l+tr[p].r)>>1; if(x<=mid) change(lc(p), x); else change(rc(p), x); pushup(p); } int query(int p, int l, int r) // 区查 { if(r<tr[p].l || tr[p].r<l) return 0; if(l<=tr[p].l && tr[p].r<=r) return tr[p].s; return query(lc(p), l, r) + query(rc(p), l, r); } int main() { int n;scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int m;scanf("%d", &m); for (int i = 1; i <= m; i++)scanf("%d%d", &q[i].l, &q[i].r),q[i].id = i; // 每个查询的编号 sort(q+1,q+m+1,[](node n1,node n2){return n1.r<n2.r;}); // 按查询右端点排序 for (int i = 1; i <= m; i++)v[q[i].r].push_back(i); // 右端点相同的查询 bt(1, 1, n); for (int i = 1; i <= n; i++)// 枚举每个数 { if (last[a[i]]) change(1, last[a[i]]); last[a[i]] = i; // 记录ai最后一次的下标 for (auto t : v[i]) // 处理右端点i的查询 ans[q[t].id] = query(1, q[t].l, q[t].r); } for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }

C52 [可持久化线段树] P1972 [SDOI2009] HH的项链

C52 可持久化线段树 P1972 [SDOI2009] HH的项链
cpp #include<bits/stdc++.h> using namespace std; template<typename T>void qr(T& x) { x=0;int f=1;char c=getchar(); for( ;!isdigit(c);c=getchar())if(c=='-')f=-1; for( ; isdigit(c);c=getchar())x=x*10+c-48; x=x*f; } template<typename T>void qw(T x) { if(x<0)x=-x,putchar('-'); if(x/10)qw(x/10); putchar(x%10+48); } const int N = 1e6+5; #define lc(p) tr[p].ls #define rc(p) tr[p].rs #define mid ((l + r) >> 1) struct node{int ls,rs,s/*s:区间数的出现次数之和*/;}tr[N*40];int trlen,rt[N],a[N],last[N]; void change(int pre,int &now, int l, int r, int x,int k)// 更新历史版本，k=1/ -1 { now=++trlen;tr[now]=tr[pre]; tr[now].s+=k; if(l==r)return; if(x<=mid)change(lc(pre), lc(now), l, mid, x,k); else change(rc(pre), rc(now), mid+1,r, x,k); } int query(int now, int l, int r, int x)// 查询[1,x]的次数 { if (l == r)return tr[now].s; if (x<=mid) return query(lc(now), l, mid, x)+tr[rc(now)].s; else return query(rc(now), mid+1, r, x); } int main(void) { int n;qr(n); for (int i = 1; i <= n; ++i)qr(a[i]); memset(last,0,sizeof(last)); trlen=0;rt[0]=0; for (int i = 1,rtt=0; i <= n; ++i) { if (!last[a[i]]) change(rt[i-1],rt[i], 1, n, i, 1); // 首次出现，直接新增版本 else { change(rt[i-1],rtt, 1, n, last[a[i]], -1); // 移除上一次位置 change(rtt, rt[i], 1, n, i, 1); // 新增当前位置 } last[a[i]] = i; // 记录当前位置 } int m;qr(m); for(int i=1,l,r;i<=m;i++) { qr(l), qr(r); qw(query(rt[r], 1, n, r) - query(rt[l-1], 1, n, l-1)); puts(""); } return 0; }

C91 树状数组+排序 P1972 [SDOI2009] HH的项链

C91 树状数组+排序 P1972 [SDOI2009] HH的项链
cpp #include<bits/stdc++.h> using namespace std; const int N = 1e6 + 10; struct node{ int l, r, id;}q[N];// 查询 vector<int> v[N]; // 右端点相同的查询 int n,a[N],lsh[N], last[N],ans[N]; int c[N]; void add(int x, int k){ for(;x<=n;x+=x&-x) c[x]+=k;} int getsum(int x) {int res=0; for(;x>=1;x-=x&-x)res+=c[x]; return res;} int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), lsh[i]=a[i]; // 离散化准备 sort(lsh+1, lsh+n+1); int ln=unique(lsh+1, lsh+n+1)-lsh-1; for(int i=1; i<=n; i++) a[i]=lower_bound(lsh+1, lsh+ln+1, a[i])-lsh; // 离散化 int m;scanf("%d", &m); for (int i = 1; i <= m; i++)scanf("%d%d", &q[i].l, &q[i].r),q[i].id = i; // 每个查询的编号 sort(q+1, q+m+1,[] (node n1, node n2){return n1.r<n2.r;}); // 按右端点排序 for (int i = 1; i <= m; i++)v[q[i].r].push_back(i); // 右端点相同的查询分组 memset(c,0,sizeof(c)); memset(last,0,sizeof(last)); for (int i = 1,p=1; i <= m; i++) // 按右端点处理 { for(;p<=q[i].r;p++) // 处理到当前右端点的所有元素 { if (last[a[p]]) add(last[a[p]],-1); // 移除上一次出现 add(p,1); // 新增当前位置 last[a[p]] = p; // 更新最后出现位置 } for (auto t : v[q[i].r]) // 处理该右端点的所有查询 ans[q[t].id] = getsum(q[t].r) - getsum(q[t].l-1); // 区间查询 } for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0; }

C35 线段树+排序（离线） P1972 [SDOI2009] HH的项链

#include <bits/stdc++.h> // 线段树+排序
using namespace std;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
const int N = 1e6 + 10;
struct tree{ int l, r, s;} tr[N * 4];
struct node{ int l, r, id;} q[N];           // 查询
vector<int> v[N]; // 右端点相同的查询
int a[N], last[N], ans[N];

void pushup(int p) { tr[p].s = tr[lc(p)].s + tr[rc(p)].s; } void bt(int p, int l, int r) // 建树 { tr[p] = {l, r, 0}; if(lr) {tr[p].s=1;return;} int mid=(l+r)>>1; bt(lc(p), l, mid); bt(rc(p), mid + 1, r); pushup(p); } void change(int p, int x) // 点修 { if(tr[p].ltr[p].r){tr[p].s= 0;return;} int mid=(tr[p].l+tr[p].r)>>1; if(x<=mid) change(lc(p), x); else change(rc(p), x); pushup(p); } int query(int p, int l, int r) // 区查 { if(r<tr[p].l || tr[p].r<l) return 0; if(l<=tr[p].l && tr[p].r<=r) return tr[p].s; return query(lc(p), l, r) + query(rc(p), l, r); }

int main() { int n;scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int m;scanf("%d", &m); for (int i = 1; i <= m; i++)scanf("%d%d", &q[i].l, &q[i].r),q[i].id = i; // 每个查询的编号

sort(q+1,q+m+1,[](node n1,node n2){return n1.r<n2.r;}); // 按查询右端点排序
for (int i = 1; i <= m; i++)v[q[i].r].push_back(i); // 右端点相同的查询

bt(1, 1, n);
for (int i = 1; i <= n; i++)// 枚举每个数
{ 
    if (last[a[i]]) change(1, last[a[i]]);
    last[a[i]] = i; // 记录ai最后一次的下标

    for (auto t : v[i]) // 处理右端点i的查询
        ans[q[t].id] = query(1, q[t].l, q[t].r);
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;

}</pre>
C52 可持久化线段树 P1972 [SDOI2009] HH的项链

#include<bits/stdc++.h>
using namespace std;
template<typename T>void qr(T& x)
{
x=0;int f=1;char c=getchar();
for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
for( ; isdigit(c);c=getchar())x=x10+c-48;
x=xf;
}
template<typename T>void qw(T x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}	
const int N = 1e6+5;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
#define mid ((l + r) >> 1)
struct node{int ls,rs,s/s:区间数的出现次数之和/;}tr[N*40];int trlen,rt[N],a[N],last[N];
void change(int pre,int &now, int l, int r, int x,int k)// 点修
{

now=++trlen;tr[now]=tr[pre];
tr[now].s+=k;
if(l==r)return;
if(x<=mid)change(lc(pre), lc(now), l,  mid, x,k);
else      change(rc(pre), rc(now), mid+1,r, x,k);
}
int query(int now, int l, int r, int x)// 点查
{
if (l == r)return tr[now].s;
if (x<=mid) return query(lc(now), l,   mid, x)+tr[rc(now)].s;
else        return query(rc(now), mid+1, r, x);
}
int main(void)
{
int n;qr(n);
for (int i = 1; i <= n; ++i)qr(a[i]);
memset(last,0,sizeof(last));
trlen=0;rt[0]=0;
for (int i = 1,rtt=0; i <= n; ++i)
{
if (!last[a[i]])  change(rt[i-1],rt[i], 1, n, i, 1);
else
{
change(rt[i-1],rtt   , 1, n, last[a[i]], -1);
change(rtt,    rt[i] , 1, n, i,           1);
}
last[a[i]] = i; // 记录ai的出现位置
}
int m;qr(m);
for(int i=1,l,r;i<=m;i++)
{
qr(l), qr(r);
qw(query(rt[r], 1, n, l));
puts("");
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct node{ int l, r, id;}q[N];// 查询
vector<int> v[N]; // 右端点相同的查询
int n,a[N],lsh[N], last[N],ans[N];
int c[N];
void add(int x, int k){ for(;x<=n;x+=x&-x) c[x]+=k;}
int getsum(int x) {int res=0; for(;x>=1;x-=x&-x)res+=c[x]; return res;}

int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), lsh[i]=a[i]; sort(lsh+1, lsh+n+1); int ln=unique(lsh+1, lsh+n+1)-lsh-1; for(int i=1; i<=n; i++) a[i]=lower_bound(lsh+1, lsh+ln+1, a[i])-lsh;

int m;scanf("%d", &m);
for (int i = 1; i <= m; i++)scanf("%d%d", &q[i].l, &q[i].r),q[i].id = i; // 每个查询的编号

sort(q+1, q+m+1,[] (node n1, node n2){return n1.r<n2.r;}); // 按查询右端点排序
for (int i = 1; i <= m; i++)v[q[i].r].push_back(i); // 右端点相同的查询

memset(c,0,sizeof(c));
memset(last,0,sizeof(last));
for (int i = 1,p=1; i <= m; i++)
{ 
    for(;p<=q[i].r;p++)
    {
        if (last[a[p]]) add(last[a[p]],-1);
        add(p,1);
        last[a[p]] = p;
    }
    for (auto t : v[q[i].r]) // 处理右端点i的查询
        ans[q[t].id] =getsum(q[t].r)-getsum(q[t].l-1);
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;

}</pre>