树状数组+离散化+转化

　　一道树状数组好题！我们先来一发弱化版：如果只查询有多少个石头，怎么做？很简单，我们需要考虑权值树状数组，先离散化（因为我们只需要考虑高矮关系），如何离散化？考虑离线，将可能改变的值都存下来，离散化一下。每次的查询通过二分来找到对应的离散化之后的值。之后就是权值树状数组的常规操作了，将之前的贡献减去，将新来的贡献加上。但是，这道题问的是有多少个连续的部分。考虑去重，如果一个点比她左边的一个点海拔要低，那么就会重复计数，那么就应该在她所对应的权值上减去1，同理，如果她比她右边的点海拔低，那么也要减1.最后查询一个数x，就是查询去掉[1,x-1]的影响后的值，可以用前缀和实现。

注意特判边界：1、n！！！！！！！！！！！！

code：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define int long long using namespace std;const int maxn=2000006;#define half (l+r)>>1struct hzw{ int rhi,hi; int id;}s[maxn];struct zmd{ int id; int x,y;}q[maxn];inline bool cmp1(hzw a,hzw b){ return a.rhi
            
             =k) { r=mid-1; ans=min(ans,s[mid].hi); } else l=mid+1; } if (ans==1e9) return tot+1; return ans;} inline void update(int x,int k){ if (!x) return; if (x>tot) return; for (int i=x;i<=tot;i+=(i&(-i))) { val[i]+=k; }}inline int query(int x){ int ans=0; if (!x) return 0; if (x>tot) x=tot; for (int i=x;i>0;i-=i&(-i)) { ans+=val[i]; } return ans;}signed main(){ cin>>n>>m; for (int i=1;i<=n;++i) { scanf("%lld",&s[i].rhi); s[i].id=i; } tot=n; for (int i=1;i<=m;++i) { scanf("%lld",&q[i].id); if (q[i].id==1) scanf("%lld",&q[i].x); else { scanf("%lld%lld",&q[i].x,&q[i].y); s[++tot].id=tot, s[tot].rhi=q[i].y; } } sort(s+1,s+1+tot,cmp1); for (int i=1;i<=tot;++i) { if (s[i].rhi==s[i-1].rhi) s[i].hi=s[i-1].hi; else s[i].hi=s[i-1].hi+1; } for (int i=1;i<=m;++i) { if (q[i].id==2) continue; q[i].x=search(q[i].x); } sort(s+1,s+1+tot,cmp2); int cnt=n; for (int i=1;i<=n;++i) { update(s[i].hi,1); update(min(s[i].hi,s[i-1].hi),-1); } for (int i=1;i<=m;++i) { if (q[i].id==1) { printf("%lld\n",query(tot)-query(q[i].x-1)); continue; } else { cnt++; update(s[q[i].x].hi,-1); if (q[i].x!=1)update(min(s[q[i].x].hi,s[q[i].x-1].hi),1); if (q[i].x!=n)update(min(s[q[i].x].hi,s[q[i].x+1].hi),1); s[q[i].x].hi=s[cnt].hi; update(s[q[i].x].hi,1); if (q[i].x!=1)update(min(s[q[i].x].hi,s[q[i].x-1].hi),-1); if (q[i].x!=n)update(min(s[q[i].x].hi,s[q[i].x+1].hi),-1); } } return 0; }
            
           
          
         
        
       
      
     
    

总结：

1、类似这样有关于值的大小比较类问题要考虑用权值版，利用巧妙地离散化解决问题。

2、这种会重复计算的要考虑怎么去重；

3、注意边界