[BZOJ1878][SDOI2009]HH的项链-白红宇

[BZOJ1878][SDOI2009]HH的项链

阅读量：4885 次

发布时间：2019-06-11

本文共 2162 字，大约阅读时间需要 7 分钟。

[BZOJ1878][SDOI2009]HH的项链

试题描述

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。

输入

第一行：一个整数N，表示项链的长度。第二行：N个整数，表示依次表示项链中贝壳的编号（编号为0到1000000之间的整数）。第三行：一个整数M，表示HH询问的个数。接下来M行：每行两个整数，L和R（1 ≤ L ≤ R ≤ N），表示询问的区间。

输出

M行，每行一个整数，依次表示询问对应的答案。

输入示例

61 2 3 4 3 531 23 52 6

输出示例

数据规模及约定

对于20%的数据，N ≤ 100，M ≤ 1000；

对于40%的数据，N ≤ 3000，M ≤ 200000；

对于100%的数据，N ≤ 50000，M ≤ 200000。

题解

找到每个颜色的前驱（即上一次出现在哪）并维护下来，那么询问时对于一个区间 [L, R]，若某个颜色为 c 的点的前驱小于 L，那么它是最靠前的颜色为 c 的点，显然，统计出有多少个“最靠前的某颜色的点的个数”，就能得到答案了。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() { if(Head == Tail) { int l = fread(buffer, 1, BufferSize, stdin); Tail = (Head = buffer) + l; } return *Head++;}int read() { int x = 0, f = 1; char c = Getchar(); while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); } while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); } return x * f;}#define maxn 50010#define maxnode 1600010#define maxc 1000010int ToT, rt[maxn], sumv[maxnode], lc[maxnode], rc[maxnode];void update(int& y, int x, int l, int r, int p) { sumv[y = ++ToT] = sumv[x] + 1; if(l == r) return ; int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x]; if(p <= mid) update(lc[y], lc[x], l, mid, p); else update(rc[y], rc[x], mid + 1, r, p); return ;}int query(int o, int l, int r, int qr) { if(!o) return 0; if(r <= qr) return sumv[o]; int mid = l + r >> 1, ans = query(lc[o], l, mid, qr); if(qr > mid) ans += query(rc[o], mid + 1, r, qr); return ans;}int lstp[maxc];int main() { int n = read(); for(int i = 1; i <= n; i++) { int col = read(); update(rt[i], rt[i-1], 0, n, lstp[col]); lstp[col] = i; } int q = read(); while(q--) { int ql = read(), qr = read(); printf("%d\n", query(rt[qr], 0, n, ql - 1) - query(rt[ql-1], 0, n, ql - 1)); } return 0;}

转载于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/6358108.html

你可能感兴趣的文章