Fruits(线段树）

题目

https://www.nowcoder.com/acm/contest/119/M

题目大意

给你n个节点，每个节点有一个值。有m个操作。操作1是区间更新值为x，操作2是查询区间被切成k段的最大“优雅值”。
优雅值的定义：几段连续的所有数字都不相同的区间中的元素个数和。如3 4 4 4 5的优雅值为4, 3 4 4 5的优雅值为3。3 4 4 5可被切成2段：{3 4}，{4 5}优雅值变为4。

算法思路

• 很明显的线段树。理解题意后我们可以知道，只需要多维护左右端点的值就可以了。区间合并的时候，只需要检查左边区间的右端点和右边区间的左端点是不是相等就可以了。
• tree[rt]：所代表区间的优雅值
  lnode[rt],rnode[rt]：所代表区间的左右端点的值

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+100;
int lnode[maxn<<2];
int rnode[maxn<<2];
int tree[maxn<<2];
int seg[maxn<<2];
void pushup(int rt){
 tree[rt]=tree[rt*2]+tree[rt*2+1];
 if(rnode[rt*2]==lnode[rt*2+1])
    tree[rt]--;
 lnode[rt]=lnode[rt*2];
 rnode[rt]=rnode[rt*2+1];
}
void pushdown(int rt){
  if(seg[rt]){
    seg[rt*2]=seg[rt];
    seg[rt*2+1]=seg[rt];
    tree[rt*2]=1;
    tree[rt*2+1]=1;
    lnode[rt*2]=rnode[rt*2]=lnode[rt*2+1]=rnode[rt*2+1]=seg[rt];
    seg[rt]=0;
  }
}
void build(int l,int r,int rt){
  seg[rt]=0;
  if(l==r) {
    scanf("%d",&lnode[rt]);
    rnode[rt]=lnode[rt];
    tree[rt]=1;
    return;
  }
  int mid=(l+r)/2;
  build(l,mid,rt*2);
  build(mid+1,r,rt*2+1);
  pushup(rt);
}
void update(int l,int r,int ll,int rr,int add,int rt){
  if(l>=ll&&r<=rr) {
    seg[rt]=add;
    lnode[rt]=rnode[rt]=add;
    tree[rt]=1;
    return;
  }
  pushdown(rt);
  int mid=(l+r)/2;
  if(ll<=mid) {
    update(l,mid,ll,rr,add,rt*2);
  }
  if(rr>mid){
    update(mid+1,r,ll,rr,add,rt*2+1);
  }
  pushup(rt);
}

int query(int l,int r,int ll,int rr,int rt){
  if(l>=ll&&r<=rr){
     return tree[rt];
  }
  int ans=0;int ans1=0;int ans2=0;
  pushdown(rt);
  int mid=(l+r)/2;
  if(ll<=mid) ans1=query(l,mid,ll,rr,rt*2);
  if(rr>mid) ans2=query(mid+1,r,ll,rr,rt*2+1);
  ans=ans1+ans2;
  if(ans1&&ans2&&rnode[rt*2]==lnode[rt*2+1]) ans--;
  return ans;
}

int main(){
  int n,m;
  while(scanf("%d%d",&n,&m)==2){
    build(1,n,1);
    for(int i=0;i<m;i++){
       int op,l,r,x;
       scanf("%d%d%d%d",&op,&l,&    //  cout<<min(r-l+1,ans+x)<<endl;r,&x);
       if(op==1){
           update(1,n,l,r,x,1);

       }
       if(op==2){
         int ans=query(1,n,l,r,1);
         printf("%d\n",min(r-l+1,ans+x));
       }
    }
  }
    return 0;
}

废话

思考清楚 这题不难。
过的人少估计是题意不清