20190709 暑训 区间种类数

?

I - Turing Tree?HDU - 3333?

这个题目求的不是区间种类数，而是求一个区间不同数加和。

这个题目第一次碰到感觉有点难，看了题解，就是首先对这个区间进行离散化，然后对于每一个查询区间对r进行排序。

为什么要对 r 进行排序呢， 笼统的说就是消去前面更新对后面的影响。

举个例子， 1 1 2 1 3? 如果查询区间是 3 5， 1 4， 1 2 ，那么排完序之后就是? 1 2，1 4，3 5

查 1 2 的之前就可以把第一个1删去，第二个1 就放到第二个位置，查1 4 是不受影响的，查4 之前会把第三个和第四个放进去，然后第2个又会被删除，

第四个又会放进去，。。。

推荐博客??这个讲的很清楚。

?

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <iostream>
#include <map>
#define inf 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int maxn = 1e5   10;
typedef long long ll;
ll sum[maxn * 8];
int a[maxn], b[maxn], vis[maxn];
struct node
{
    int l, r, id;
    ll ans;
}ex[maxn];

bool cmp1(node a,node b)
{
    return a.r < b.r;
}

bool cmp2(node a,node b)
{
    return a.id < b.id;
}

void push_up(int id)
{
    sum[id] = sum[id << 1]   sum[id << 1 | 1];
    //printf("sum[%d]=%lld\n", id, sum[id]);
}

void update(int id,int l,int r,int pos,int val)
{
    if(l==r)
    {
        sum[id] = val;
    //    printf("  sum[%d]=%d\n", id, val);
        return;
    }
    int mid = (l   r) >> 1;
    if (pos <= mid) update(id << 1, l, mid, pos, val);
    else update(id << 1 | 1, mid   1, r, pos, val);
    push_up(id);
}

ll query(int id,int l,int r,int x,int y)
{
    if(x<=l&&y>=r) return sum[id];
    int mid = (l   r) >> 1;
    ll ans = 0;
    if (x <= mid) ans  = query(id << 1, l, mid, x, y);
    if (y > mid) ans  = query(id << 1 | 1, mid   1, r, x, y);
    return ans;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, m;
        scanf("%d", &n);
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; i  ) scanf("%d", &a[i]), b[i] = a[i];
        sort(b   1, b   1   n);
        int len = unique(b   1, b   1   n) - b - 1;
        for(int i=1;i<=n;i  )
        {
            a[i] = lower_bound(b   1, b   1   n, a[i]) - b;
        }
        scanf("%d", &m);
        for (int i = 1; i <= m; i  ) scanf("%d%d", &ex[i].l, &ex[i].r), ex[i].id = i;
        sort(ex   1, ex   1   m, cmp1);
        memset(vis, 0, sizeof(vis));
        int k = 1;
        for(int i=1;i<=n;i  )
        {
            if(vis[a[i]])
            {
                update(1, 1, n, i, b[a[i]]);
                update(1, 1, n, vis[a[i]], 0);
                vis[a[i]] = i;
            }
            else
            {
                update(1, 1, n, i, b[a[i]]);
                vis[a[i]] = i;
            }
            //printf("a[%d]=%d b[%d]=%d\n", i, a[i], a[i], b[a[i]]);
            while(i==ex[k].r&&k<=m)
            {
                ex[k].ans = query(1, 1, n, ex[k].l, ex[k].r);
                k  ;
            }
        }
        sort(ex   1, ex   1   m, cmp2);
        for (int i = 1; i <= m; i  ) printf("%lld\n", ex[i].ans);
    }
    return 0;
}

线段树

?

区间种类数

这个和上面那个很类似，基本上是一样的。

?

来源：https://www./content-4-339251.html