[线段树][优化][特征分析] HDU 4027 Can you answer these queries?

https://cn.vjudge.net/problem/HDU-4027

这个题，本身并没有用到区间修改的什么操作。。如果不加优化就基本可以认为是单点修改区间查询的线段树，但是int64的最大值也只需要6次开根号就会收敛到1，因此我们可以加一个优化就是当子区间每一个都是1的话就不再更新区间（就这一个优化真的可以搞定吗。。。）其他的都跟普通的线段树一样了，只不过初始化建树的时候需要一个单独的点修改函数来操作。


//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=2e6+100;
//const int MOD=1e9+7;
const int INF=0x4f4f4f4f;
const int maxnode=6e6+5;


LL edu[maxn<<2],addv[maxn<<2];

void built()
{
    edu[1]=0;
    addv[1]=0;
}

void pushdown(int o)
{
    if(addv[o])
    {
        addv[o<<1]+=addv[o],addv[(o<<1)+1]+=addv[o];
        addv[o]=0;
    }
}

void maintain(int o,int l, int r)
{
    int lc=o<<1,rc=(o<<1)+1;
    if(r>l)
        edu[o]=edu[lc]+edu[rc];
    else 
        edu[o]=(LL)sqrt(1.0*edu[o]);
}

int pl,pr,pos;
LL v;
void change(int o,int l,int r)//单独的点修改，这不能用那个update了因为那个有sqrt操作
{
    if(l==r)
        edu[o]=v;
    else
    {
        int mid=(l+r)>>1;
        if(pos<=mid)change(o<<1,l,mid);
        else change((o<<1)+1,mid+1,r);
        edu[o]=edu[o<<1]+edu[(o<<1)+1];
    }

}

void update(int o,int l,int r)//更新
{
    if(pl<=l&&r<=pr)//本来是区间修改的打标记，这里变成了优化
    {
        if(edu[o]==r-l+1)//wtf?
            return ;
    }
    if(r>l)
    {
        int mid=(l+r)>>1;
        if(pl<=mid)
            update(o<<1,l,mid);
        if(pr>mid)
            update((o<<1)+1,mid+1,r);
    }
    maintain(o,l,r);//维护区间和，如果是叶子则sqrt
}

int ql,qr;

LL query(int o,int l,int r)
{
    if(ql<=l&&r<=qr)//包括了叶子节点的情况
    {
        return edu[o];
    }
    else if(r>l)
    {
        LL ans=0;
        //pushdown(o);
        int mid=(l+r)>>1;
        if(ql<=mid)
            ans+=query(o<<1,l,mid);
        if(qr>mid)
            ans+=query((o<<1)+1,mid+1,r);
        return ans;
    }
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    int n,m,op,a,b,c,cnt=0;
    while(~scanf("%d",&n))
    {
        cnt++;
        built();
        for (int i=1;i<=n;i++)
        {
            scanf("%lld",&v);
            pos=i;
            change(1,1,n);
        }
        scanf("%d",&m);
        printf("Case #%d:\n",cnt);
        while(m--)
        {
            scanf("%d %d %d",&op,&a,&b);
            if(a>b)
                swap(a,b);
            if(!op)
            {
                pl=a,pr=b;//,v=c;
                update(1,1,n);
            }
            else
            {
                ql=a,qr=b;

                printf("%lld\n",query(1,1,n));
            }
        }
        puts("");
    }
    return 0;
}

一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

发表回复 取消回复

发表回复取消回复