1冊の通は編の木の形の配列を高めて題集をします

前奏
木の配列の問題をする前に、3つの板の問題をする必要があります.
ボード1——単点修正、区間照会
板子题就不写题解了哈
コード#コード#

#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
int n,q,a[1000005],c[1000005];
void update(int t,int v)
{
    for (int x=t; x<=n; x+=x&-x) c[x]+=v;
}
int getsum(int t)
{
    int ans=0;
    for (int x=t; x; x-=x&-x) ans+=c[x];
    return ans;
}
signed main()
{
    scanf("%lld%lld",&n,&q);
    for (int i=1; i<=n; i++) scanf("%lld",&a[i]),update(i,a[i]);
    for (int i=1; i<=q; i++){
        int x,l,r;
        scanf("%lld%lld%lld",&x,&l,&r);
        if (x==1) update(l,r);
        if (x==2) printf("%lld
",getsum(r)-getsum(l-1));
    }
    return 0;
}

板子題2——区間修正、単点照会
コード#コード#

#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;
int n,q,a[1000005],c[1000005];
void update(int x,int v)
{
    for (; x<=n; x+=x&-x) c[x]+=v;
}
int getsum(int x)
{
    int sum=0;
    for (; x>0; x-=x&-x) sum+=c[x];
    return sum;
}
signed main()
{
    scanf("%lld",&n);
    scanf("%lld",&q);
    int last=0;
    for (int i=1; i<=n; i++) {scanf("%lld",&a[i]); update(i,a[i]-last); last=a[i];}
    for (int i=1; i<=q; i++){
        int f;
        scanf("%lld",&f);
        if (f==1) {
            int x,y,v;
            scanf("%lld%lld%lld",&x,&y,&v);
            update(x,v); update(y+1,-v);
        }
        else{
            long long ans; int x;
            scanf("%lld",&x);
            ans=getsum(x);
            printf("%lld
",ans);
        }
    }
}

板子題3——区間修正、区間照会
コード#コード#

#include
#include
#define ll long long
using namespace std;
int n,q;
ll a[1000005],c1[1000005],c2[1000005];
void update(int x,int v)
{
    for (int X=x; X<=n;X+=X&-X) c1[X]+=v,c2[X]+=(ll)v*x;
}
ll getsum(int x)
{
    ll sum=0;
    for (int X=x; X>0; X-=X&-X) sum+=(ll)(x+1)*c1[X]-c2[X];
    return sum;
}
int main()
{
    scanf("%d%d",&n,&q);
    for (int i=1; i<=n; i++) scanf("%lld",&a[i]),a[i]+=a[i-1];
    while (q--){
        char st[3];
        scanf("%s",st);
        if (st[0]=='2'){
            int x,y;
            scanf("%d%d",&x,&y);
            printf("%lld
",getsum(y)-getsum(x-1)+a[y]-a[x-1]); 
        }
        else {
            int x,y,v;
            scanf("%d%d%d",&x,&y,&v);
            update(x,v); update(y+1,-v);
        }
    }
    return 0;
}

正式に問題を塗ります!!
T 1——星を数えるUral 1028/loj 10114
問題解
入力時にテーマが並べ替えられているため、並べられたデータであればy軸とは関係なく、現在の星の級数は、その星の前のすべてのx軸がその星のx軸の大きさに等しい数の和より小さいと推理されている.これからは楽しくコードをコードできます~~~
コード#コード#

#include
#include
#include
#include
#include
#include
using namespace std;
int n,a[1000005],c[1000005],ans[1000005];
void update(int x,int v)
{
    for (; x<=40000; x+=x&-x) c[x]+=v;
}
int getsum(int x)
{
    int ans=0;
    for (; x; x-=x&-x) ans+=c[x];
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1; i<=n; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x++;
        ans[getsum(x)]++;
        update(x,1);
    }
    for (int i=1; i<=n; i++) printf("%d
",ans[i-1]);
    return 0;
}

T 2——校門外の木vijos 1148loj 10115
問題解
この問題を括弧シーケンスに変換し、区間に1つの木を植えることはlの位置に1つを加えることに相当する(,r rの位置に1つの右括弧を加える.2つの木状配列を維持し、1つは左括弧を記録し、1つは右括弧を記録し、答えは叫び出した.
コード#コード#

#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,c[1000005][2],a[1000005];
void update(int x,int y,int t)
{
    for (; x<=n; x+=x&-x) c[x][t]+=y;
}
int getsum(int x,int t)
{
    int ans=0;
    for (; x; x-=x&-x) ans+=c[x][t];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++){
        int x,l,r;
        scanf("%d%d%d",&x,&l,&r);
        if (x==1) update(l,1,0),update(r,1,1);
        if (x==2) printf("%d
",getsum(r,0)-getsum(l-1,1));
    }
    return 0;
}

T 3——点検人数loj 10116
問題解
木の形の配列は裸で問題を書きます~~、書きません
コード#コード#

#include
#include
#include
#include
#include
#include
using namespace std;
int n,k,c[1000005];
char ch[1005];
void update(int x,int y)
{
    for (; x<=n; x+=x&-x) c[x]+=y;
}
int getsum(int x)
{
    int ans=0;
    for (; x; x-=x&-x) ans+=c[x];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1; i<=k; i++){
        scanf("%s",ch);
        if (ch[0]=='A') {
            int x;
            scanf("%d",&x);
            printf("%d
",getsum(x));
        }
        if (ch[0]=='B'){
            int x,y;
            scanf("%d%d",&x,&y);
            update(x,y);
        }
        if (ch[0]=='C'){
            int x,y;
            scanf("%d%d",&x,&y);
            update(x,-y);
        }
    }
    return 0;
}

T 4——[CQOI 2006]簡単問題loj 10117
問題解
高仿T 2,多说したくない
コード#コード#

#include
#include
#include
#include
#include
#include
using namespace std;
int n,m,c[1000005][2];
void update(int x,int y,int t)
{
    for (; x<=n; x+=x&-x) c[x][t]+=y;
}
int getsum(int x,int t)
{
    int ans=0;
    for (; x; x-=x&-x) ans+=c[x][t];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++){
        int x; scanf("%d",&x);
        if (x==1) {
            int l,r;
            scanf("%d%d",&l,&r);
            update(l,1,0); update(r,1,1);
        }
        if (x==2){
            int t; scanf("%d",&t);
            printf("%d
",(getsum(t,0)-getsum(t-1,1))&1);
        }
    }
    return 0;
}

よし、これだけ辛いことを書いても、たくさん書いても意味がないじゃないか.