[SDOI2009]HH的项链-白红宇

[SDOI2009]HH的项链

阅读量：6928 次

发布时间：2019-06-27

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

OJ题号：BZOJ1878、洛谷1972

思路：树状数组离线化。

不难想到，对于一个[l,r]的区间，如果出现了多个相同的颜色，我们可以只关心在区间[l,r]中，该颜色最后一个贝壳。

例如，对于形如{1,2,3,2,1}的项链，当我们询问区间[1,5]时，该项链等同于{0,0,3,2,1}（方便起见，这里用0表示空）。

于是就有了以下的思路：当询问[l,r]时，答案即为区间[l,r]内新出现的贝壳的个数。

显而易见，当新的贝壳出现时，原来的同色贝壳都会失效。

那么问题来了，对于{1,2,3,2,1}这个项链，当我们询问[1,5]时，答案是3；当我们询问[1,3]时，答案也是3，但如果使用上面的方法，我们记录的是{0,0,3,2,1}，输出的答案是1。怎么办？

一种思路是使用可持久化数据结构，比如主席树（可持久化线段树）等。然而当时主席树似乎并没有被发明？

这里介绍一种离散化做法。

首先对所有的询问预处理，即以右端点r为关键字进行排序。

建立一个树状数组，记录每个前缀新出现的贝壳的个数。

当然树状数组并不能一次性建好，每次根据当前询问的r，加入位置≤r的所有贝壳（将树状数组中的位置标记为1），并删去相同颜色的贝壳（将树状数组中的位置标记为0）。

然后发现洛谷上能A，在BZOJ上就RE了？

最后发现的原因：代表颜色的数字不一定是连续的，而且可能会很大（编号为0到1000000之间的整数），所以直接开数组会爆，解决的方法是Hash（不方便）或者Map。

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
2084658			Accepted	4668 kb	1488 ms	/	1324 B	2017-05-27 17:34:54

1 #include 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define r first 7 #define l second.first 8 #define id second.second 9 typedef std::pair
          
           
             > Q;10 const int N=50001;11 int n;12 class FenwickTree {13 private:14 int val[N];15 int lowbit(const int x) {16 return x&-x;17 }18 public:19 FenwickTree() {20 memset(val,0,sizeof val);21 }22 void modify(int p,const int x) {23 while(p<=n) {24 val[p]+=x;25 p+=lowbit(p);26 }27 }28 int query(int p) {29 int ans=0;30 while(p) {31 ans+=val[p];32 p-=lowbit(p);33 }34 return ans;35 }36 };37 FenwickTree tree;38 int main() {39 scanf("%d",&n);40 int a[n+1];41 for(int i=1;i<=n;i++) {42 scanf("%d",&a[i]);43 }44 int m;45 scanf("%d",&m);46 Q q[m];47 for(int i=0;i
            
              last;54 int ans[m];55 for(int i=0;i

转载于:https://www.cnblogs.com/skylee03/p/6913749.html

你可能感兴趣的文章