A simple Blog for wyx I've been down the bottle hoping.
BZOJ 3038 上帝造题的7分钟二
发表于: | 分类: Oi | 评论:0 | 阅读:139

XLk觉得《上帝造题的七分钟》不太过瘾,于是有了第二部。
"第一分钟,X说,要有数列,于是便给定了一个正整数数列。
第二分钟,L说,要能修改,于是便有了对一段数中每个数都开平方(下取整)的操作。
第三分钟,k说,要能查询,于是便有了求一段数的和的操作。
第四分钟,彩虹喵说,要是noip难度,于是便有了数据范围。
第五分钟,诗人说,要有韵律,于是便有了时间限制和内存限制。
第六分钟,和雪说,要省点事,于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。"
——《上帝造题的七分钟·第二部》
所以这个神圣的任务就交给你了。

md,线段树开了LL,结果读入的数组忘开了……制杖
我们来看正解吧
我们只需要开线段树统计,每一次进行单点修改
但是暴力的每一次修改会T
我们加上一个小优化,如果已经是0/1了就不需要再改了,可以把这个标记上传上去……
这是一个好方法,时间复杂度就是近似的$nlog(n)*30$
还是可做的

#include <cmath>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
const int N = 100000+5;
const int M = N << 2;
using namespace std;
typedef long long LL;

LL tr[M],lazy[M];
LL a[N],n;

inline void updata(int k){
    tr[k] = tr[k<<1] + tr[k<<1|1];
    lazy[k] = lazy[k<<1] & lazy[k<<1|1];
}

inline void build(int k,int l,int r){
    if(l==r){
        tr[k] = a[l];
        if(tr[k] == 0 || tr[k] == 1)lazy[k] = 1;
        return ;
    }
    int mid = (l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    updata(k);
}

void change(int k,int l,int r,int x,int y){
    if(lazy[k]) return;
    if(l==r){
        tr[k] = (LL)sqrt(tr[k]);
        if(tr[k] == 0 || tr[k] == 1) lazy[k] = 1; return;
    }
    int mid = (l+r)>>1;
    if(y <= mid) change(k<<1,l,mid,x,y);
    else if(x>mid)change(k<<1|1,mid+1,r,x,y);
    else change(k<<1,l,mid,x,mid),change(k<<1|1,mid+1,r,mid+1,y);
    updata(k);
}

LL ask(int k,int l,int r,int x,int y){
    if(l==x && r==y)return tr[k];
    int mid = (l+r)>>1;
    if(y<=mid)return ask(k<<1,l,mid,x,y);
    else if(x>mid)return ask(k<<1|1,mid+1,r,x,y);
    else return ask(k<<1,l,mid,x,mid)+ask(k<<1|1,mid+1,r,mid+1,y);
}

inline LL read(){
    LL x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main(){
    n = read();
    for(int i=1;i<=n;++i)a[i] = read();
    build(1,1,n);int m = read();
    while(m--){
        int opt = read(),x = read(),y = read(); if(x>y)swap(x,y);
        if(opt == 0) change(1,1,n,x,y);
        else printf("%lld\n",ask(1,1,n,x,y));
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP