Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- struct a{
- int bestleft, bestright, wholesum, bestsum;
- };
- a seg[1000000];
- int arr[1000000];
- void update(int s, int e, int us, int ue, int k, int idx){
- if(s>=us && e<=ue){
- seg[idx].wholesum+=k;
- //cout<<seg[idx].wholesum;
- return;
- }
- else if(e<us || s>ue){
- return;
- }
- int mid=(s+e)/2;
- update(mid+1, e, us, ue, k, idx*2+1);
- update(s, mid, us, ue, k, idx*2);
- seg[idx].wholesum=seg[idx*2].wholesum+seg[idx*2+1].wholesum;
- //cout<<seg[idx].wholesum<<endl;
- }
- void update1(int s, int e, int us, int ue, int idx){
- if(s>=us && e<=ue){
- seg[idx].bestleft=seg[idx].wholesum;
- seg[idx].bestright=seg[idx].wholesum;
- return;
- }
- else if(e<us || s>ue)
- return;
- int mid=(s+e)/2;
- update1(mid+1, e, us, ue, idx*2+1);
- update1(s, mid, us, ue, idx*2);
- seg[idx].bestleft=max(seg[idx*2].bestleft, seg[idx*2].wholesum+seg[idx*2+1].bestleft);
- seg[idx].bestright=max(seg[idx*2+1].bestright, seg[idx*2+1].wholesum+seg[idx*2].bestright);
- }
- void update2(int s, int e, int us, int ue, int idx){
- if(s>=us && e<=ue){
- seg[idx].bestsum=seg[idx].wholesum;
- return;
- }
- else if(e<us || s>ue)
- return;
- int mid=(s+e)/2;
- update2(mid+1, e, us, ue, idx*2+1);
- update2(s, mid, us, ue, idx*2);
- seg[idx].bestsum=max(max(seg[idx*2].bestsum, seg[idx*2+1].bestsum), seg[idx*2].bestright+seg[idx*2+1].bestleft);
- }
- int query(int s, int e, int us, int ue, int idx){
- if(s==us && e==ue)
- return seg[idx].bestsum;
- else if(e<us || s>ue)
- return 0;
- int mid=(s+e)/2;
- return query(mid+1, e, us, ue, idx)+query(s, mid, us, ue, idx);
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin>>n;
- for(int i=0; i<n; i++){
- cin>>arr[i];
- update(1, n, i+1, i+1, arr[i], 1);
- }
- for(int i=0; i<n; i++)
- update1(1, n, i+1, i+1, 1);
- for(int i=0; i<n; i++)
- update2(1, n, i+1, i+1, 1);
- //for(int i=1; i<=7; i++){
- //cout<<seg[i].bestleft<<" "<<seg[i].bestright<<" "<<seg[i].bestsum<<" "<<seg[i].wholesum<<endl;
- //}
- int m;
- cin>>m;
- for(int i=0; i<m; i++){
- int a, b;
- cin>>a>>b;
- query(1, n, a, b, 1);
- //cout<<query(1, n, a, b, 1)<<endl;
- }
- //for(int i=1; i<=5; i++){
- //cout<<seg[i].bestsum<<endl;
- //}
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement