[题解]A Simple Problem with Integers

题目链接(QAQ戳我)
题目是对一个数组,支持两种操作
操作C:对下标从a到b的每个元素,值增加c;
操作Q:对求下标从a到b的元素值之和。
Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

这是道很水的比较有代表性的模板题(还可以用多种办法A掉)最典型的办法是树状数组,线段树,还有分块。
我还是太弱了,比不得Qiuly大佬水黑题那么强无敌(%%%),只好写写最简单的树状数组和分块的题解了。

分块:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
template<typename T>void scan(T &x)
{
    x=0;char ch;bool f=0;
    ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(f==1) x=-x;
}
long long n,m,x;
long long bash;
long long k,s=1;
int wei[100005];
struct fen
{
    long long zuo;
    long long you;
    long long s[400];
    long long sum;
    long long summ;
}kuai[400];
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scan(n);
    bash=sqrt(n);
    scan(m);
    kuai[1].zuo=1;
    for(register long long i=1;i<=n;i++)
    {
        k++;
        if(k>bash) ++s,kuai[s-1].you=i-1,k=1,kuai[s].zuo=i;
        scan(kuai[s].s[k]);
        kuai[s].sum+=kuai[s].s[k];
        wei[i]=s;
    }
    kuai[s].you=n;
    /*
    cout<<bash<<" "<<s<<endl;
    for(register int i=1;i<=s;i++)
    {
        for(register int j=1;j<=kuai[i].you-kuai[i].zuo+1;j++)
            printf("%d ",kuai[i].s[j]);
        putchar('\n');
    }
    cout<<endl<<endl;*/
    for(register int i=1;i<=m;i++)
    {
        /*cout<<endl;
        for(register int j=1;j<=s;j++)
            for(register int k=1;k<=kuai[j].you-kuai[j].zuo+1;k++)
                cout<<kuai[j].s[k]+kuai[j].summ<<" ";
        cout<<endl;
        */
        int x,y,z;
        char ch;
        cin>>ch;
        if(ch=='Q')
        {
            long long ans=0;
            scan(x);
            scan(y);
            //cout<<x<<" "<<y<<"  ";
            if(wei[y]-wei[x]>=2)
            {
                for(register int j=wei[x]+1;j<=wei[y]-1;j++)
                    ans+=kuai[j].sum+(kuai[j].summ*(kuai[j].you-kuai[j].zuo+1));
                for(register int j=x;j<=kuai[wei[x]].you;j++)
                    ans+=kuai[wei[x]].s[j-kuai[wei[x]].zuo+1]+kuai[wei[x]].summ;
                for(register int j=kuai[wei[y]].zuo;j<=y;j++)
                    ans+=kuai[wei[y]].s[j-kuai[wei[y]].zuo+1]+kuai[wei[y]].summ;
            }
            else if(wei[y]-wei[x]==1)
            {
                for(register int j=x;j<=kuai[wei[x]].you;j++)
                    ans+=kuai[wei[x]].s[j-kuai[wei[x]].zuo+1]+kuai[wei[x]].summ;
                for(register int j=kuai[wei[y]].zuo;j<=y;j++)
                    ans+=kuai[wei[y]].s[j-kuai[wei[y]].zuo+1]+kuai[wei[y]].summ;
            }
            else
                for(register int j=x;j<=y;j++)
                    ans+=kuai[wei[y]].s[j-kuai[wei[x]].zuo+1]+kuai[wei[y]].summ;
            printf("%lld\n",ans);        
        }
        else if(ch=='C')
        {
            scan(x);
            scan(y);
            scan(z);
            if(wei[y]-wei[x]>=2)
            {
                for(register int j=wei[x]+1;j<=wei[y]-1;j++)
                    kuai[j].summ+=z;
                for(register int j=x;j<=kuai[wei[x]].you;j++)
                    kuai[wei[x]].s[j-kuai[wei[x]].zuo+1]+=z,kuai[wei[x]].sum+=z;
                for(register int j=kuai[wei[y]].zuo;j<=y;j++)
                    kuai[wei[y]].s[j-kuai[wei[y]].zuo+1]+=z,kuai[wei[y]].sum+=z;    
            }
            else if(wei[y]-wei[x]==1)
            {
                for(register int j=x;j<=kuai[wei[x]].you;j++)
                    kuai[wei[x]].s[j-kuai[wei[x]].zuo+1]+=z,kuai[wei[x]].sum+=z;
                for(register int j=kuai[wei[y]].zuo;j<=y;j++)
                    kuai[wei[y]].s[j-kuai[wei[y]].zuo+1]+=z,kuai[wei[y]].sum+=z;
            }
            else
                for(register int j=x;j<=y;j++)
                    kuai[wei[y]].s[j-kuai[wei[x]].zuo+1]+=z,kuai[wei[x]].sum+=z;
        }
    }
    return 0;
}

树状数组:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
template<typename T>void scan(T &x)
{
    x=0;char ch;bool f=0;
    ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if(ch=='-') f=1,ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(f==1) x=-x;
}
long long n,m;
long long sum[100005],c[100005],b[100005],c1[100005];
long long ask(int x)
{
    long long ans=0;
    for(;x;x-=(x&-x)) ans+=c[x];
    return ans;
}
void add(int x,long long y)
{
    for(;x<=n;x+=(x&-x)) c[x]+=y;
}
long long ask1(int x)
{
    long long ans=0;
    for(;x;x-=(x&-x)) ans+=c1[x];
    return ans;
}
void add1(int x,long long y)
{
    for(;x<=n;x+=(x&-x)) c1[x]+=y;
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scan(n);
    scan(m);
    for(register int i=1;i<=n;i++)
        scan(b[i]);
    for(register int i=1;i<=n;i++)
        sum[i]+=sum[i-1]+b[i];
    for(register int i=1;i<=m;i++)
    {
        char ch;
        cin>>ch;
        if(ch=='Q')
        {
            long long l,r;
            scan(l);
            scan(r);
            printf("%lld\n",((r+1)*ask(r)-l*ask(l-1))+sum[r]-sum[l-1]+ask1(l-1)-ask1(r));
        }
        else 
        {
            long long l,r,z;
            scan(l);
            scan(r);
            scan(z);
            add(l,z);
            add(r+1,-z);
            add1(l,l*z);
            add1(r+1,-(r+1)*z);
            for(register int j=1;j<=n;j++)cout<<c[j]<<" ";
            cout<<endl;
            for(register int j=1;j<=n;j++)cout<<c1[j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

小蒟蒻我就不写注释了QAQ。

Last modification:April 15th, 2019 at 03:27 pm

2 comments

  1. marTixx

    orztql , 我还不会分块啊 ,不过链接地址好像少了些什么,还有记得加上POJ的题号和此题的标签哦ヾ(≧∇≦*)ゝ

  2. Qiuly

    嗯说实话实际上数据结构这种东西什么操作不要一个劲的往main里面堆,可以开个namespace或者struct,然后再将数据结构的所有的函数丢到里面就好了,这个样子会方便看得多.....可以康康窝线段树怎么写的自我觉得挺好看的。另外对于这类问题分块只是下下策,线段树简单维护就好了。分块一般解决更加恶心的问题,也就是线段树维护不了的,如区间众数,就像蒲公英这一题一样ヾ(≧∇≦*)ゝ

Leave a Comment