Submission #67750972

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ex exit(0)
#define ln cout<<'\n'
#define ll long long
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.12f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

class RMQ{
public:
  int n;
  P dat[2222222];
  void init(int _n){
    n=1;
    while(n<_n)n*=2;
    rep(i,2*n) dat[i]=P(-MAXL,-1);
  }
  void update(int k,P a){
    k+=n-1;dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=max(dat[k*2+1],dat[k*2+2]);
    }
  }
  P query(int a,int b){return query(a,b,0,0,n);}
  P query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return P(-MAXL,-1);
    if(a<=l&&r<=b) return dat[k];
    P vl=query(a,b,k*2+1,l,(l+r)/2);
    P vr=query(a,b,k*2+2,(l+r)/2,r);
    return max(vl,vr);
  }
};

RMQ t;

set<ll> se[26];
set<P> s[26];
ll m=1;
void IN(P p,ll k) {
  iter(s[k]) it=s[k].upper_bound(P(p.F,MAXL));
  if(it!=s[k].begin()) {
    it--;
    P q=*it;
    if(q.F<=p.F&&p.F<=q.S||abs(p.F-q.F)<=m||abs(p.F-q.S)<=m) {
      p.F=min(p.F,q.F);
      p.S=max(p.S,q.S);
      s[k].erase(it);
      t.update(q.F,P(-MAXL,-1));
    }
  }
  while(1) {
    it=s[k].upper_bound(P(p.F,-1));
    if(it==s[k].end()) break;
    P q=*it;
    if(abs(p.S-q.F)>m&&abs(q.S-p.F)>m) break;
    else {
      p.F=min(p.F,q.F);
      p.S=max(p.S,q.S);
      s[k].erase(it);
      t.update(q.F,P(-MAXL,-1));
    }
  }
  s[k].in(p);
  t.update(p.F,P(p.S-p.F,p.F));
}

void DEL(P p,ll k) {
  iter(s[k]) it=s[k].upper_bound(P(p.F,MAXL));
  vector<P> v;
  if(it!=s[k].begin()) {
    it--;
    P q=*it;
    if(q.F!=p.F) {
      iter(se[k]) it2=se[k].lower_bound(p.F);
      if(it2!=se[k].begin()) {
        it2--;
        v.pb(P(q.F,*it2));
      }
    }
    if(q.S!=p.F) {
      iter(se[k]) it2=se[k].lower_bound(p.F);
      if(it2!=se[k].end()) {
        v.pb(P(*it2,q.S));
      }
    }
    s[k].erase(it);
    t.update(q.F,P(-MAXL,-1));
  }
  if(v.size()==2&&abs(v[0].S-v[1].F)<=m) {
    v[0].S=v[1].S;
    v.pop_back();
  }
  rep(i,v.size()) {
    s[k].in(v[i]);
    t.update(v[i].F,P(v[i].S-v[i].F,v[i].F));
  }
}


void Init() {}
void Main() {
  ll n,T;
  string e;
  cin >> n >> T >> e;
  t.init(n);
  rep(i,n) {
    ll k=e[i]-'a';
    se[k].in(i);
    IN(P(i,i),k);
  }
  while(T--) {
    ll z;
    R z;
    if(z==1) {
      ll x;
      char c;
      cin >> x >> c;
      x--;
      ll k=e[x]-'a';
      se[k].erase(x);
      DEL(P(x,x),k);
      e[x]=c;
      k=e[x]-'a';
      se[k].in(x);
      IN(P(x,x),k);
    } else {
      ll l,r;
      cin >> l >> r;
      l--,r--;
      P p=t.query(l,r+1);
      ll x=p.S,y=x+p.F;
      ll ans=min(y,r)-x+1;
      if(r<y) {
        t.update(p.S,P(-MAXL,-1));
        P q=t.query(l,r+1);
        ll x2=q.S,y2=x2+q.F;
        ans=max(ans,min(y2,r)-x2+1);
        t.update(p.S,p);
      }
      rep(i,26) {
        iter(s[i]) it=s[i].lower_bound(P(l,-1));
        if(it!=s[i].begin()) {
          it--;
          P q=*it;
          if(l<=q.S) ans=max(ans,min(r,q.S)-l+1);
        }
      }
      pr(ans);
    }
  }


}

int main(){ios::sync_with_stdio(0);cin.tie(0);Init();ll T=1;if(0)R T;while(T--)Main();return 0;}

Submission Info

Compile Error

Main.cpp: In function ‘void IN(P, long long int)’:
Main.cpp:61:16: warning: suggest parentheses around ‘&&’ within ‘||’ [-Wparentheses]
   61 |     if(q.F<=p.F&&p.F<=q.S||abs(p.F-q.F)<=m||abs(p.F-q.S)<=m) {
      |                ^

Judge Result