Can you answer these queries?

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 12193    Accepted Submission(s): 2892

Problem Description
A lot of battleships of evil are arranged in a line before the battle. Our commander decides to use our secret weapon to eliminate the battleships. Each of the battleships can be marked a value of endurance. For every attack of our secret weapon, it could decrease
the endurance of a consecutive part of battleships by make their endurance to the square root of it original value of endurance. During the series of attack of our secret weapon, the commander wants to evaluate the effect of the weapon, so he asks you for
help.
You are asked to answer the queries that the sum of the endurance of a consecutive part of the battleship line.

Notice that the square root operation should be rounded down to integer.

 
Input
The input contains several test cases, terminated by EOF.
  For each test case, the first line contains a single integer N, denoting there are N battleships of evil in a line. (1 <= N <= 100000)
  The second line contains N integers Ei, indicating the endurance value of each battleship from the beginning of the line to the end. You can assume that the sum of all endurance value is less than 2 63.
  The next line contains an integer M, denoting the number of actions and queries. (1 <= M <= 100000)
  For the following M lines, each line contains three integers T, X and Y. The T=0 denoting the action of the secret weapon, which will decrease the endurance value of the battleships between the X-th and Y-th battleship, inclusive. The T=1 denoting the query
of the commander which ask for the sum of the endurance value of the battleship between X-th and Y-th, inclusive.
 
Output
For each test case, print the case number at the first line. Then print one line for each query. And remember follow a blank line after each test case.
 
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
Case #1:
19
7
6
 
Source

The 36th ACM/ICPC Asia Regional
Shanghai Site —— Online Contest

This problem needs to open a large array of line tree , And use it long long. Due to the use sqrt, So it can be used when the values in the node or interval are 1 It doesn't go down update, It is lazy thought .

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
long long dur[15040000];
inline void pushup(int k)
{dur[k]=dur[k<<1]+dur[k<<1|1];}
inline void build(int s,int t,int k)
{
if(!(s^t)){
scanf("%I64d",&dur[k]);
return;
}int m=(s+t)>>1;
build(s,m,k<<1);
build(m+1,t,k<<1|1);
pushup(k);
}
inline void update(int s,int t,int k,int l,int r)
{
if(dur[k]==t-s+1)return;
if(!(s^t)){
dur[k]=sqrt(dur[k]);
return;
}int m=(s+t)>>1;
if(l<=m)update(s,m,k<<1,l,r);
if(m<r)update(m+1,t,k<<1|1,l,r);
pushup(k);
}
inline long long query(int s,int t,int k,int l,int r)
{
if(l<=s&&t<=r)return dur[k];
int m=(s+t)>>1;
long long res=0;
if(l<=m)res+=query(s,m,k<<1,l,r);
if(m<r)res+=query(m+1,t,k<<1|1,l,r);
return res;
}
int main()
{
int n,m,cas=0;
while(scanf("%d",&n)!=EOF){
build(1,n,1);
scanf("%d",&m);
printf("Case #%d:\n",++cas);
for(;m;m--){
int T,a,b;
scanf("%d%d%d",&T,&a,&b);
if(a>b)swap(a,b);
if(!T)update(1,n,1,a,b);
else printf("%I64d\n",query(1,n,1,a,b));
}puts("");
}
return 0;
}

hdu 4027 More articles about

  1. HDU 4027 Can you answer these queries?( Single point update of line tree + Interval query )

    Topic link The question : Here you are. N Number , Conduct M operations ,0 The operation is to change every number in the interval into its own square root ( Integers ),1 The operation is to find the sum of intervals . Ideas : Single point update , Interval query , That is to pay attention to the optimization when updating , Otherwise, it will time out , Because of all the ...

  2. HDU 4027—— Can you answer these queries?——————【 Section tree interval square root , Sum of intervals 】

    Can you answer these queries? Time Limit:2000MS     Memory Limit:65768KB     64bit IO Format:%I64d & ...

  3. HDU 4027 Can you answer these queries?( Section tree interval square root )

    Can you answer these queries? Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65768/65768 K ...

  4. HDU 4027( Line segment tree )

    HDU4027 The question : The operation instruction is 0 when , For the interval [x,y] Square the number between : Instructions for 1 When , For the interval [x,y] Sum the numbers between and output : Ideas : Line tree processing is OK 了 , however 64 The number of bits is the most open 8 The second square is 1 了 ( open ...

  5. Can you answer these queries? HDU 4027 Line segment tree

    Can you answer these queries? HDU 4027 Line segment tree The question I mean, there's a way 1 To the numbered ship , Every ship has its own combat value , Then we have a secret weapon , It can change the combat value of a ship from a number to the original ...

  6. V - Can you answer these queries? HDU - 4027 Line segment tree violence

    V - Can you answer these queries? HDU - 4027 There is no idea at the beginning of this topic , Because I don't know how to update the open root of interval . Then I took a look at the solution , Because the root of every number is the most ...

  7. hdu 4027 Can you answer these queries?

    Topic linking http://acm.hdu.edu.cn/showproblem.php?pid=4027 Can you answer these queries? Description Proble ...

  8. hdu 4027 Can you answer these queries? Segment tree interval root , Sum of intervals

    Can you answer these queries? Time Limit: 1 Sec  Memory Limit: 256 MB Topic linking http://acm.hdu.edu.cn/sho ...

  9. hdu 4027 2011 Shanghai online competition G Line segment tree Square root of a segment ***

    You can't use the one that increases or decreases in segments directly , Because the square root of a sum is not equal to the sum of the square roots , Whether the direct record is 1, yes 1 There's no need to update #include<cstdio> #include<iostream> # ...

Random recommendation

  1. And contract it out Future: Code level control timeout

    Thank you Doug Lea. Use scenarios : Recently doing webservice When called , Find a problem , The other person's webservice The interface is very unstable , So when we get the data, we often have to wait a long time to pull all the data back , Sometimes even directly ...

  2. boost serialize

    #include <iostream> #include <boost/serialization/serialization.hpp> #include <boost/ ...

  3. YUI Modular development

    As Internet applications become more and more important ,js The code is getting bigger and bigger , How to organize your own code effectively , Become very important . We should learn to control our code , Not to the last pile bug I don't know where it came from . The modular development of the front end can help us effectively manage ...

  4. Detailed explanation JDBC Connect to database

    One . Concept 1. In order to make the program operate the database , Operate on the tables in the database , Each database will provide a set of drivers to connect and operate the database , And the drivers for each database are different , for example mysql Database usage mysql drive ,oracle Count ...

  5. CENTOS6.6 Next nmon Monitoring of

    This article comes from my github pages Blog http://galengao.github.io/ namely www.gaohuirong.cn Installing Nmon By default nmon is ...

  6. 【 machine learning 】--FP-groupth From the beginning to the application of the algorithm

    One . Foregoing Two . structure FP_groupth Count the flow 1. Scan transaction database D once . Collect a collection of frequent items F And their support . Yes F Sort in descending order of support , The result is a list of frequent items L. 2. establish FP Root node of tree , With “null” Mark it ...

  7. [BZOJ 4516] [SDOI 2016] Create a spell

    Description The spell string consists of many spell characters , Spell characters can be represented by numbers . For example, you can use the spell character 1.2 Put it together to form a magic string [1,2]. A string of charms S The nonempty string of is called the magic string S The magic spell of generation . example ...

  8. BigDecimal Some precautions in use

    Java Business Computing , Out-of-service float and double, Because they can't do accurate calculations . however Java The designer of provides a very useful class for programmers BigDecimal, He can perfect float and double Class can't count exactly ...

  9. The service gateway zuul Of the six :Zuul High availability

    We actually use Zuul The way is shown in the figure above , Different clients use different loads to distribute requests to back-end Zuul,Zuul Through Eureka Call back end service , Finally, export . So in order to guarantee Zuul High availability , The front end can start multiple at the same time Zuu ...

  10. [APIO2018] Duathlon Iron man two

    Without going through the point , Think about double Dot double , Consider the cube tree Two points s,t, On the middle path , All the points in the dot pair can pass through , Specially ,s,t As a cut point , You can't go back , That is, you can't go through the square points behind you That is to say ,(s,t) Through all the circles in the path of the tree ...