題目

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

題目大意

給你n個(gè)節(jié)點(diǎn)腊满，每個(gè)節(jié)點(diǎn)有一個(gè)值免姿。有m個(gè)操作岖是。操作1是區(qū)間更新值為x行您，操作2是查詢區(qū)間被切成k段的最大“優(yōu)雅值”轴咱。
優(yōu)雅值的定義：幾段連續(xù)的所有數(shù)字都不相同的區(qū)間中的元素個(gè)數(shù)和汛蝙。如3 4 4 4 5的優(yōu)雅值為4, 3 4 4 5的優(yōu)雅值為3。3 4 4 5可被切成2段：{3 4}朴肺，{4 5}優(yōu)雅值變?yōu)?窖剑。

算法思路

• 很明顯的線段樹。理解題意后我們可以知道戈稿，只需要多維護(hù)左右端點(diǎn)的值就可以了西土。區(qū)間合并的時(shí)候，只需要檢查左邊區(qū)間的右端點(diǎn)和右邊區(qū)間的左端點(diǎn)是不是相等就可以了鞍盗。
• tree[rt]：所代表區(qū)間的優(yōu)雅值
  lnode[rt],rnode[rt]：所代表區(qū)間的左右端點(diǎn)的值

代碼

#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;
}

廢話

思考清楚 這題不難需了。
過的人少估計(jì)是題意不清