luogu1972：HH的项链-白红宇

luogu1972：HH的项链

阅读量：4552 次

发布时间：2019-06-08

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

题目描述HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。输入输出格式输入格式：第一行：一个整数N，表示项链的长度。第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。第三行：一个整数M，表示HH 询问的个数。接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。输出格式：M 行，每行一个整数，依次表示询问对应的答案。输入输出样例输入样例#1：61 2 3 4 3 531 23 52 6输出样例#1：224说明数据范围：对于100%的数据，N <= 50000，M <= 200000。

题目

芒果君：昨天躺在床上想了半天，直到今天吃早饭才想出20分暴力，隐隐约约感觉要前缀和，还要把查询按左端点排序，不过后面觉得没用就都删了。结果离正解越来越远QAQ………………暴力：预处理找到当前数下一次出现的位置jp，查询l~r扫一遍，要是jp在区间内就说明有重复的数。那不就是说重复的数里只有一个是对答案有贡献的，最左最右都可以。用树状数组维护，如果是最左，一开始只将数字第一次出现的位置加入，查询排序，再扫一遍1~n，看有哪些查询可以做了，然后当前的数字就会失效，应该把它的jp加入。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #include
            
              9 #include
             
              10 #include
              
               11 #include
               
                12 #define inf 1<<2913 using namespace std;14 typedef long long ll;15 inline int read()16 {17 int ret(0);18 char ch=getchar();19 while(ch<'0'||ch>'9') ch=getchar();20 while(ch>='0'&&ch<='9'){21 ret=ret*10+ch-'0';22 ch=getchar();23 }24 return ret;25 }26 struct Query{27 int l,r,id,ans;28 }q[200010];29 int n,m,pre[1000010],l,r,cnt=1,jp[50010],tree[50010],x;30 bool cmp1(Query x,Query y)31 {32 if(x.l==y.l) return x.r
                
                 m) break;66 }67 sort(q+1,q+m+1,cmp2);68 for(int i=1;i<=m;++i) printf("%d\n",q[i].ans);69 return 0;70 }

转载于:https://www.cnblogs.com/12mango/p/7644303.html

你可能感兴趣的文章