线段树板子

package ICPC;  
import java.util.*;  
import java.math.*;  
import java.io.*;  
import java.text.DecimalFormat;  
import java.text.NumberFormat;  
class node{
    int l,r,max,cnt;
}
public class Main {  
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));  
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));  
    static StringTokenizer tokenizer = new StringTokenizer("");  
    static String next() throws IOException {  
        while (!tokenizer.hasMoreTokens()) {  
            tokenizer = new StringTokenizer(reader.readLine());  
        }  
        return tokenizer.nextToken();  
    }  
    static int nextInt() throws IOException {  
        return Integer.parseInt(next());  
    }  
 
    static int N=200010,n,m;
    static node tr[]=new node[4*N];
    static int w[]=new int[N];
    public static void main(String[] args)throws IOException {
        n=nextInt();
        m=nextInt();
        
        for(int i=1;i<=n;i++)w[i]=nextInt();
        
        for(int i=0;i<4*N;i++)tr[i]=new node();
        
        builder(1,1,n);

        while(m-->0) {
            String s=reader.readLine();
            
            String ss[]=s.split(" ");
            int l=Integer.parseInt(ss[1]),r=Integer.parseInt(ss[2]);
            
            if(ss[0].equals("Ask")) {
//                builder(1,1,n);
                int t[]=query(1,l,r);
                pw.println(t[0]+" "+t[1]);
            }else {
                update(1,l,r);
            }
        }
        pw.flush();
    }

    private static void update(int rt, int x, int v) {
        int lc=rt<<1,rc=rt<<1|1;
        
        if(tr[rt].l==x&&tr[rt].r==x) {
            tr[rt].max=v;
            return;
        }
        int mid=(tr[rt].l+tr[rt].r)>>1;
        if(x<=mid)update(lc,x,v);
        if(x>mid)update(rc,x,v);
        pushup(rt);
        
    }

    private static int[] query(int rt, int l, int r) {
        int lc=rt<<1,rc=rt<<1|1;
        if(l<=tr[rt].l&&r>=tr[rt].r) {
            return new int[] {tr[rt].max,tr[rt].cnt};
        }
        
        int mid=(tr[rt].l+tr[rt].r)>>1;
        int sum[]=new int[2];
        if(l<=mid) {
            int t[]=query(lc,l,r);
            if(t[0]>sum[0]) {
                sum[0]=t[0];
                sum[1]=t[1];
            }else if(t[0]==sum[0]) {
                sum[1]+=t[1];
            }
        }
        if(r>mid) {
            int t[]=query(rc,l,r);
            
            if(t[0]>sum[0]) {
                sum[0]=t[0];
                sum[1]=t[1];
            }else if(t[0]==sum[0]) {
                sum[1]+=t[1];
            }
        }
        
        return sum;
    }

    private static void builder(int rt, int l, int r) {
        int lc=rt<<1,rc=rt<<1|1;
        tr[rt].l=l;tr[rt].r=r;tr[rt].max=w[l];tr[rt].cnt=1;
        if(l==r)return;
        int mid=l+r>>1;
        if(l<=mid)builder(lc,l,mid);
        if(r>mid)builder(rc,mid+1,r);
        if(tr[lc].max==tr[rc].max) {
            tr[rt].max=tr[lc].max;
            tr[rt].cnt=tr[lc].cnt+tr[rc].cnt;
        }else if(tr[lc].max>tr[rc].max) {
            tr[rt].max=tr[lc].max;
            tr[rt].cnt=tr[lc].cnt;
        }else {
            tr[rt].max=tr[rc].max;
            tr[rt].cnt=tr[rc].cnt;
        }
    }

    private static void pushup(int rt) {
        
        int lc=rt<<1,rc=rt<<1|1;
        
        if(tr[lc].max==tr[rc].max) {
            tr[rt].max=tr[lc].max;
            tr[rt].cnt=tr[lc].cnt+tr[rc].cnt;
        }else if(tr[lc].max>tr[rc].max) {
            tr[rt].max=tr[lc].max;
            tr[rt].cnt=tr[lc].cnt;
        }else {
            tr[rt].max=tr[rc].max;
            tr[rt].cnt=tr[rc].cnt;
        }
    }
}