I Hate It(線分ツリー区間最値+更新区間)

9029 ワード

多くの学校では比較的な習慣が流行している.先生たちは聞くのが好きで、○○から○○までの中で、点数が一番高いのはいくらですか.
これは多くの学生に反感を抱かせた.
あなたが喜ぶかどうかにかかわらず、今あなたがしなければならないのは、先生の要求に従って、プログラムを書いて、先生の質問をシミュレートすることです.もちろん、先生はある同級生の成績を更新する必要があることがあります.
Inputこの問題には複数のテストが含まれています.ファイルが終わるまで処理してください.各試験の1行目には、2つの正の整数NとM(0学生ID番号はそれぞれ1からNに編成される.2行目はN個の整数を含み、このN個の学生の初期成績を表し、i番目の数はIDがiの学生の成績を表す.次はM行である.各行には1つの文字C(‘Q’または‘U’のみ)と2つの正の整数A,Bがある.Cが「Q」である場合、IDがAからB(A,Bを含む)までの学生の中で、成績が最も高いかを尋ねる質問操作であることを示す.Cが「U」の場合、IDがAの学生の成績をBに変更する更新操作であることを示す.Outputは,問合せ操作ごとに1行に最高成績を出力する.Sample Input

Sample Output

Hint

Huge input,the C function scanf() will work better than cin

#include 
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include <set>
#include 
#include 
#include 
using namespace std;
#define pq priority_queue
#define pql priority_queue
#define pqn priority_queue
#define v vector
#define vl vector
#define lson rt<<1, l, m
#define rson rt<<1|1, m+1, r
#define read(x) scanf("%d",&x)
#define lread(x) scanf("%lld",&x);
#define pt(x) printf("%d
",(x))
#define yes printf("YES
");
#define no printf("NO
");
#define gcd __gcd
#define out(x) cout<#define over cout<#define rep(j,k) for (int i = (int)(j); i <= (int)(k); i++)
#define input(k) for (int i = 1; i <= (int)(k); i++)  {cin>>a[i] ; }
#define mem(s,t) memset(s,t,sizeof(s))
#define re return ;
#define ok return 0;
#define TLE std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod(x) ((x)%9973)
#define test cout<#define ls now<<1
#define rs now<<1|1
const int N=201000+100;
typedef struct node
{
    int val,l,r,sum,mx,mn,lazy;
    //int mid() {return (l+r)>>1;}
}node;
node dp[N*4];
int a[N],maxn;
void upsum(int now) {    dp[now].sum = dp[ls].sum+dp[rs].sum;    }
void upmx(int now)  {    dp[now].mx = max(dp[ls].mx,dp[rs].mx);  }
void build(int now,int l,int r)
{
    dp[now].l=l,dp[now].r=r;
    if(dp[now].l==dp[now].r)    {        dp[now].mx = a[l]; re ;    }
    int mid = (l+r)>>1;
    build(ls,l,mid);
    build(rs,1+mid,r);
    upmx(now);
}
void querymx(int now,int l,int r)
{
    if(dp[now].l>=l && dp[now].r<=r) {maxn = max(dp[now].mx,maxn);re;}
    int mid = (dp[now].l+dp[now].r)>>1;
    if(l<=mid)
        querymx(ls,l,r);
    if(r>mid)
        querymx(rs,l,r);

}
void upnode(int now,int l,int k)
{
    if(dp[now].l==dp[now].r&&dp[now].l==l)
    {
        dp[now].mx = k;
        re;
    }
    int mid =(dp[now].l+dp[now].r)>>1;
    if(l<=mid)
        upnode(ls,l,k);
    else
        upnode(rs,l,k);
    dp[now].mx=max(dp[ls].mx,dp[rs].mx);
}


int main()
{
    string str;int ll,rr,n,m;
    TLE;
    while(cin>>n>>m)
    {
        input(n);
        build(1,1,n);
        rep(1,m)
        {
            cin>>str>>ll>>rr;
            if(str[0]=='Q')
            {
                maxn = -1;
                querymx(1,ll,rr);
                cout<endl;
            }
            else
                upnode(1,ll,rr);
        }
    }
    ok;
}

ORM for Net主流フレームワークの要約と効率テスト

ZZULIOJ.1095:間隔(マルチインスタンステスト)