膾炙人口雙倍經(jīng)驗(yàn)
2492 上帝造題的7分鐘 2
時(shí)間限制: 1 s
空間限制: 64000 KB
題目等級(jí) : 大師 Master
題目描寫 Description
XLk覺得《上帝造題的7分鐘》不太過癮，因而有了第2部。
“第1分鐘，X說，要有數(shù)列，因而便給定了1個(gè)正整數(shù)數(shù)列。
第2分鐘，L說，要能修改，因而便有了對(duì)1段數(shù)中每一個(gè)數(shù)都開平方(下取整)的操作。
第3分鐘，k說，要能查詢，因而便有了求1段數(shù)的和的操作。
第4分鐘，彩虹喵說，要是noip難度，因而便有了數(shù)據(jù)范圍。
第5分鐘，詩(shī)人說，要有韻律，因而便有了時(shí)間限制和內(nèi)存限制。
第6分鐘，和雪說，要省點(diǎn)事，因而便有了保證運(yùn)算進(jìn)程中及終究結(jié)果均不超過64位有符號(hào)整數(shù)類型的表示范圍的限制。
第7分鐘，這道題終究造完了，但是，造題的神牛們不再想寫這道題的程序了?！?
――《上帝造題的7分鐘?第2部》
所以這個(gè)神圣的任務(wù)就交給你了。
輸入描寫 Input Description
第1行1個(gè)整數(shù)n，代表數(shù)列中數(shù)的個(gè)數(shù)。
第2行n個(gè)正整數(shù)，表示初始狀態(tài)下數(shù)列中的數(shù)。
第3行1個(gè)整數(shù)m，表示有m次操作。
接下來m行每行3個(gè)整數(shù)k,l,r，k=0表示給[l,r]中的每一個(gè)數(shù)開平方(下取整)，k=1表示詢問[l,r]中各個(gè)數(shù)的和。
UPD：注意數(shù)據(jù)中有可能l>r，所以遇到這類情況請(qǐng)交換l和r。
輸出描寫 Output Description
對(duì)詢問操作，每行輸出1個(gè)回答。
樣例輸入 Sample Input
10
1 2 3 4 5 6 7 8 9 10
5
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8
樣例輸出 Sample Output
19
7
6
數(shù)據(jù)范圍及提示 Data Size & Hint
對(duì)30%的數(shù)據(jù)，1
對(duì)100%的數(shù)據(jù)，1
注意l有可能大于r，遇到這類情況請(qǐng)交換l,r。
來源：Nescafe 20
和花神游歷各國(guó)完全1樣233
直接代碼(其實(shí)再發(fā)這篇我是為了訪問量和經(jīng)驗(yàn))
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 100100
#define MAXM 201000
#define lchild rt<<1,l,mid
#define rchild rt<<1|1,mid+1,r
#define ln rt<<1
#define rn rt<<1|1
using namespace std;
struct seg
{
int l,r;
long long sum,maxn;
}tree[MAXN<<4];
int n,m;
int op,l,r;
void push_up(int rt)
{
tree[rt].sum=tree[ln].sum+tree[rn].sum;
tree[rt].maxn=max(tree[ln].maxn,tree[rn].maxn);
}
void build(int rt=1,int l=1,int r=n)
{
int mid=(l+r)>>1;
tree[rt].l=l;tree[rt].r=r;
if (l==r)
{
scanf("%lld",&tree[rt].sum);
tree[rt].maxn=tree[rt].sum;
return;
}
build(lchild);build(rchild);
push_up(rt);
}
void modify(int rt,int l,int r)
{
if (tree[rt].maxn<=1) return;
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;
if (L==R)
{
tree[rt].sum=floor(sqrt(tree[rt].sum));
tree[rt].maxn=tree[rt].sum;
return;
}
if (l<=mid) modify(ln,l,r);
if (r>mid) modify(rn,l,r);
push_up(rt);
}
long long query(int rt,int l,int r)
{
int L=tree[rt].l,R=tree[rt].r,mid=(L+R)>>1;
if (L==l&&R==r) return tree[rt].sum;
if (r<=mid) return query(ln,l,r);
else
if (l>mid) return query(rn,l,r);
else return query(ln,l,mid)+query(rn,mid+1,r);
}
int main()
{
scanf("%d",&n);
build();
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&op,&l,&r);
if (l>r) swap(l,r);
if (op==1)
printf("%lld
",query(1,l,r));
else
modify(1,l,r);
}
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
