rt，复杂度正确，全部TLE。

#include<bits/stdc++.h>
using namespace std;
struct Data{int l,r,maxx,cmax,cntm,cntc;}t[1000005];
//分别表示区间起点和终点，最大值和次大值，最大值个数和次大值个数
int n,q,a[200005];
Data pushup(Data x,Data y)//合并两个区间
{
  int w[4]={x.maxx,x.cmax,y.maxx,y.cmax};
  Data ans;
  ans.l=x.l,ans.r=y.r;
  ans.maxx=ans.cmax=0;
  ans.cntm=ans.cntc=0;
  for(int i=0;i<4;i++)
  {
    if(w[i]==ans.maxx||w[i]==ans.cmax) continue;
    if(w[i]>ans.maxx) ans.cmax=ans.maxx,ans.maxx=w[i];
    else if(w[i]>ans.cmax) ans.cmax=w[i];
  }//求最大值和次大值
  if(ans.maxx==x.maxx) ans.cntm+=x.cntm;
  if(ans.maxx==y.maxx) ans.cntm+=y.cntm;
  if(ans.maxx==x.cmax) ans.cntm+=x.cntc;
  if(ans.maxx==y.cmax) ans.cntm+=y.cntc;
  if(ans.cmax==x.maxx) ans.cntc+=x.cntm;
  if(ans.cmax==y.maxx) ans.cntc+=y.cntm;
  if(ans.cmax==x.cmax) ans.cntc+=x.cntc;
  if(ans.cmax==y.cmax) ans.cntc+=y.cntc;
  //记录最大值和次大值个数
  return ans;
}
void build(int k,int l,int r)
{
  t[k].l=l,t[k].r=r;
  if(l==r)
  {
    t[k].maxx=a[l];
    t[k].cntm=1;
    t[k].cntc=0;
    return;
  }
  int mid=l+r>>1;
  build(k*2,l,mid);
  build(k*2+1,mid+1,r);
  t[k]=pushup(t[k*2],t[k*2+1]);
  return;
}
void update(int k,int l,int x)
{
  if(t[k].l==l&&t[k].r==l)
  {
    t[k].maxx=x;
    return;
  }
  int mid=t[k].l+t[k].r>>1;
  if(l<=mid) update(k*2,l,x);
  else update(k*2+1,l,x);
  t[k]=pushup(t[k*2],t[k*2+1]);
  return;
}
Data query(int k,int l,int r)
{
  if(t[k].l==t[k].r) return t[k];
  int mid=t[k].l+t[k].r>>1;
  Data ans;
  if(l<=mid) ans=query(k*2,l,r);
  if(r>mid)
  {
    if(l<=mid) ans=pushup(ans,query(k*2+1,l,r));
    else ans=query(k*2+1,l,r);
  }
  return ans;
}
int main()
{
  ios::sync_with_stdio(0);
  cin>>n>>q;
  for(int i=1;i<=n;i++) cin>>a[i];
  build(1,1,n);
  while(q--)
  {
    int op,x,y;
    cin>>op>>x>>y;
    if(op==1) update(1,x,y);
    else cout<<query(1,x,y).cntc<<"\n";
  }
  return 0;
}