HDU 4638 Group (莫队算法||线段树离散查询)-白红宇

HDU 4638 Group (莫队算法||线段树离散查询)

阅读量：5051 次

发布时间：2019-06-12

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

题目地址：

先写了一发莫队，莫队能够水过。非常easy的莫队，不多说。

代码例如以下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;#define LL long long#define pi acos(-1.0)#pragma comment(linker, "/STACK:1024000000")const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;int a[MAXN];LL ha[MAXN], ans[MAXN], res;struct node { int l, r, id, pos;} fei[MAXN];bool cmp(node x, node y){ return x.pos
                
                 
                  fei[i].r) { tmp=a[r]; reduce(tmp); r--; } while(r
                  
                   fei[i].l) { l--; tmp=a[l]; add(tmp); } ans[fei[i].id]=res; } for(i=0; i

然后又看了解题报告，发现线段树+离线查询也能够过。并且感觉非常奇妙的做法。。

首先先离线保存下来。然后从左向右维护，维护的是前面的值对于当前枚举值的相对个数。对于当前第i个数来说，先将这个数的值更新为1。代表一个独立的串，然后找a[i]-1和a[i]+1前面存在不存在，假设存在的话，则说明前面的这两个数已经不能作为独立的串了。相对于a[i]来说，能够共存在a[i]的串中，所以就要将a[i]-1和a[i]+1分别-1.然后再在r值为i的询问中，直接线段树求和就能够了。代码例如以下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                using namespace std;#define LL long long#define pi acos(-1.0)#pragma comment(linker, "/STACK:1024000000")#define root 1, n, 1#define lson l, mid, rt<<1#define rson mid+1, r, rt<<1|1const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;int a[MAXN], pos[MAXN], sum[MAXN<<2], ans[MAXN];struct node{ int l, r, id;}fei[MAXN];bool cmp(node x, node y){ return x.r
                
                 >1; if(p<=mid) Update(p,x,lson); else Update(p,x,rson); PushUp(rt);}int Query(int ll, int rr, int l, int r, int rt){ if(ll<=l&&rr>=r){ return sum[rt]; } int mid=l+r>>1, ans=0; if(ll<=mid) ans+=Query(ll,rr,lson); if(rr>mid) ans+=Query(ll,rr,rson); return ans;}int main(){ int t, n, m, i, j; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&a[i]); pos[a[i]]=i; } for(i=0;i
                 
                  1&&pos[a[i]-1]

转载于:https://www.cnblogs.com/jzdwajue/p/7168649.html

你可能感兴趣的文章