tyvj 1039忠誠2

P 1039忠誠2時間:1000 ms/空間:131072 KiB/Javaクラス名:Main説明

            。         10 ，             。       k  ，        ，             。          ，            。                     ，        1，2，3…  ，           ，      ： a b           ？                    。
                  

入力フォーマット
入力の最初の行には2つの数mがあり、nはm(m<=10000000)の帳簿があり、nはnの問題があり、n<=10000000である.次に、動作ごとに3つの数字、1番目のpは数字1または数字2、2番目の数はx、3番目の数はy、p=1はx、y区間はp=2はx番目の数をy出力フォーマットに変更する
出力ファイルの各質問に対する答え.サンプルを具体的に表示します.試験例1
入力
10 3 1 2 3 4 5 6 7 8 9 10 1 2 7 2 0 1 10出力
2 0セグメントツリー区間クエリー+単点修正

#include
#include
#include
using namespace std;
struct edge
{
    int value;
};
edge node[400001];
int n,m,i,p,q,z,a[400001];

void update(int s)
{
    node[s].value=min(node[s*2].value,node[s*2+1].value);
}

void build(int s,int l,int r)
{
    if (l==r)
      {
        node[s].value+=a[l];
        return;
      }
    build(s*2,l,(l+r)/2);
    build(s*2+1,(l+r)/2+1,r);
    update(s);
}

int insert(int s,int l,int r,int x,int y)
{
    int mid,ans;
    if (x<=l && y>=r)
      return node[s].value;
    mid=(l+r)/2;
    if (x<=mid)
      ans=insert(s*2,l,mid,x,y);
    else
      ans=INT_MAX;
    if (y>mid)
      ans=min(ans,insert(s*2+1,mid+1,r,x,y));
    return ans;
}

void change(int s,int l,int r,int x,int y)
{
    int mid;
    if (l==r && l==x)
      {
        node[s].value=y;
        return;
      }
    mid=(l+r)/2;
    if (x<=mid)
      change(s*2,l,mid,x,y);
    else
      change(s*2+1,mid+1,r,x,y);
    update(s);
}

int main()
{
    scanf("%d %d",&n,&m);
    for (i=1;i<=n;i++)
      scanf("%d",&a[i]);
    build(1,1,n);
    for (i=1;i<=m;i++)
      {
        scanf("%d %d %d",&p,&q,&z);
        if (p==1)
          printf("%d ",insert(1,1,n,q,z));
        if (p==2)
          change(1,1,n,q,z);
      }
    return 0;
}