膾炙人口雙倍經驗
2492 上帝造題的7分鐘 2
時間限制: 1 s
空間限制: 64000 KB
題目等級 : 大師 Master
題目描寫 Description
XLk覺得《上帝造題的7分鐘》不太過癮，因而有了第2部。
“第1分鐘，X說，要有數列，因而便給定了1個正整數數列。
第2分鐘，L說，要能修改，因而便有了對1段數中每一個數都開平方(下取整)的操作。
第3分鐘，k說，要能查詢，因而便有了求1段數的和的操作。
第4分鐘，彩虹喵說，要是noip難度，因而便有了數據范圍。
第5分鐘，詩人說，要有韻律，因而便有了時間限制和內存限制。
第6分鐘，和雪說，要省點事，因而便有了保證運算進程中及終究結果均不超過64位有符號整數類型的表示范圍的限制。
第7分鐘，這道題終究造完了，但是，造題的神牛們不再想寫這道題的程序了。”
――《上帝造題的7分鐘?第2部》
所以這個神圣的任務就交給你了。
輸入描寫 Input Description
第1行1個整數n，代表數列中數的個數。
第2行n個正整數，表示初始狀態下數列中的數。
第3行1個整數m，表示有m次操作。
接下來m行每行3個整數k,l,r，k=0表示給[l,r]中的每一個數開平方(下取整)，k=1表示詢問[l,r]中各個數的和。
UPD：注意數據中有可能l>r，所以遇到這類情況請交換l和r。
輸出描寫 Output Description
對詢問操作，每行輸出1個回答。
樣例輸入 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
數據范圍及提示 Data Size & Hint
對30%的數據，1
對100%的數據，1
注意l有可能大于r，遇到這類情況請交換l,r。
來源：Nescafe 20
和花神游歷各國完全1樣233
直接代碼(其實再發這篇我是為了訪問量和經驗)
#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網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
