线段树,死在了样例,求助
查看原帖
线段树,死在了样例,求助
379071
jjAAjj楼主2021/6/13 16:54
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
//#include<map>
#include<vector>
#include<math.h>
using namespace std;
//#define int long long
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define INF 1e9
#define ll long long
#define MAXN 900005
const int _x[]={0,1,0,-1,0},_y[]={0,0,1,0,-1};
#define mem(a,n) memset(a,n,sizeof(a));
#define chkmax(a,b) a=a>b?a:b;
#define chkmin(a,b) a=a<b?a:b;
#include<set>
#include<stack>
#define DE puts("check");
#define lc i<<1
#define rc i<<1|1
#define int long long
inline int read(){
  char c=getchar();
  while(c<'0'||c>'9'){
    if(c=='A'){
      return 1;
    }
    else if(c=='B'){
      return 2;
    }
    else if(c=='C'){
      return 3;
    }
    c=getchar();
  }
  int ans=0;
  while(c>='0'&&c<='9'){
      ans=ans*10+c-'0';
      c=getchar();
  }
  return ans;
}
typedef struct Seg_tree{
  int l,r;
  int lazy;
  int val;
}Tree;
Tree tree[MAXN*4];
void update(int i){
  tree[i].val=(tree[lc].val==tree[rc].val)?tree[lc].val:-1;
}
void push_down(int i){
  if(tree[i].lazy){
    tree[lc].val=tree[rc].val=tree[lc].lazy=tree[rc].lazy=tree[i].lazy;
    tree[i].lazy=0;
  }
}
int ch[MAXN];
void build(int i,int l,int r){
//  tree[i].l=l,tree[i].r=r;
  if(l==r){
    tree[i].val=ch[l]-'A'+1;
    return;
  }
  int mid=l+r>>1;
  build(lc,l,mid),build(rc,mid+1,r);
  update(i);
}
void change(int i,int L,int R,int l,int r,int p){
  if(l<=L&&r>=R){
    tree[i].val=tree[i].lazy=p;
    return;
  }
  int mid=L+R>>1;
  push_down(i);
  if(l<=mid){
    change(lc,L,mid,l,r,p);
  }
  if(r>mid){
    change(rc,mid+1,R,l,r,p);
  }
  update(i);
}
int query(int i,int L,int R,int p){
	if(L==R){
		return tree[i].val;
	}
	push_down(i);
	int mid=L+R>>1;
	if(p<=mid){
		return query(i*2,L,mid,p);
	}
	if(p>mid){
		return query(i*2+1,mid+1,R,p);
	}
}
int check(int i,int L,int R,int l,int r){
  int ans,pl=-2,pr=-2;
  if(l<=L&&r>=R){
    return tree[i].val;
  }
  push_down(i);
  int mid=L+R>>1;
  if(l<=mid){
    pl=check(lc,L,mid,l,r);
  }
  if(r>mid){
    pr=check(rc,mid+1,R,l,r);
  }
  if(pl==MAXN||pr==MAXN){
    return (pl==MAXN)?pr:pl;
  }
  if(pl!=MAXN&&pr!=MAXN){
    return (pl==pr)?pl:-1;
  }
}
int n,k;
signed main(){
  scanf("%lld",&n);
  scanf("%s",ch+1);
  build(1,1,n);
  scanf("%lld",&k);
  forr(i,1,k){
    int opt,l,r,x;
    opt=read();
    scanf("%lld%lld",&l,&r);
    switch(opt){
      case 1:{
        x=read();
//        DE;
        change(1,1,n,l,r,x);
        break;
      }
      case 2:{
        int ql=-2,qr=-2;
//        DE
        ql=(l==1)?0:query(1,1,n,l-1);
//        DE
        qr=(r==n)?0:query(1,1,n,r+1);
//        DE
        int tot=check(1,1,n,l,r);
//        DE
        if((ql==qr&&ql&&qr)){
          puts("No");
        }
        else{
          int ans=check(1,1,n,l,r);
          if(ans<0){
            puts("No");
          }
          else puts("Yes");
        }
        break;
      }
    }
  }
}

个人感觉没什么问题 但是样例它就是过不去 求助,样例一直输出 No

2021/6/13 16:54
加载中...