NC16034. 修改序列值
描述
输入描述
第一行一个整数n
接下来n行，每行一个整数a[i]
接下来一行一个整数q
接下来q行，每行两个用空格分隔的整数x[i],y[i]，表示把a[x[i]]修改为y[i]
输出描述
q行，每行一个整数表示答案
示例1
输入:
4 3 6 6 4 3 4 4 3 5 1 8
输出:
10 10 13
C++14(g++5.4) 解法, 执行用时: 161ms, 内存消耗: 16348K, 提交时间: 2018-05-29 21:32:04
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<map>
using namespace std;
const long long inf=1e18;
int a[110000],n,num_q,na[110000];
struct segment_tree
{
int l,r;
bool pl,pr,cover[2];
long long sum[2][2];
};
segment_tree awp;
segment_tree tree[1<<18];
void merge(segment_tree ll,segment_tree rr,segment_tree &now)
{
int i,j,s,p,q;
now.pl=ll.pl;
now.cover[0]=now.cover[1]=false;
if(ll.cover[0]&&a[ll.r]<a[rr.l])
{
now.pl^=rr.pl;
if(rr.cover[0])
now.cover[0]=true;
}
now.pr=rr.pr;
if(rr.cover[1]&&a[ll.r]>=a[rr.l])
{
now.pr^=ll.pr;
if(ll.cover[1])
now.cover[1]=true;
}
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
if(a[ll.r]>=a[rr.l])
{
if(!ll.cover[1])
now.sum[i][j]=ll.sum[i][0]+rr.sum[ll.pr][j];
else
now.sum[i][j]=ll.sum[i][0]+rr.sum[ll.pr^i][j];
}
else
{
if(!rr.cover[0])
now.sum[i][j]=ll.sum[i][rr.pl]+rr.sum[0][j];
else
{
now.sum[i][j]=ll.sum[i][rr.pl^j]+rr.sum[0][j];
}
}
}
}
void build(int left,int right,int id)
{
int i,j,l=2*id+1,r=2*id+2,mid=(left+right)>>1;
tree[id].l=left;
tree[id].r=right;
if(left==right)
{
for(i=0;i<2;i++)
for(j=0;j<2;j++)
tree[id].sum[i][j]=0;
tree[id].sum[0][0]=a[left];
tree[id].cover[0]=tree[id].cover[1]=true;
tree[id].pl=tree[id].pr=1;
return;
}
build(left,mid,l);
build(mid+1,right,r);
merge(tree[l],tree[r],tree[id]);
}
void update(int pos,int y,int id)
{
int l=2*id+1,r=2*id+2,i,j,left,right;
left=tree[id].l;
right=tree[id].r;
if(left==right)
{
for(i=0;i<2;i++)
for(j=0;j<2;j++)
tree[id].sum[i][j]=0;
tree[id].sum[0][0]=a[left];
tree[id].pl=tree[id].pr=1;
tree[id].cover[0]=tree[id].cover[1]=true;
return;
}
if(tree[l].r<pos)
update(pos,y,r);
else
update(pos,y,l);
merge(tree[l],tree[r],tree[id]);
}
int main()
{
scanf("%d",&n);
int i,j,s,p,q,x,y;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
build(0,n-1,0);
scanf("%d",&num_q);
while(num_q--)
{
scanf("%d%d",&x,&y);
x--;
a[x]=y;
update(x,y,0);
printf("%lld\n",tree[0].sum[0][0]);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 178ms, 内存消耗: 6496K, 提交时间: 2018-05-25 20:29:37
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
#define pb push_back
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
#define mpr make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) x=(x+(y))%mod
#define N 100009
using namespace std;
int n,m,a[N],b[N];
struct node{ ll ans; bool u,v; }T[N<<2][2][2];
node solve(int l,int r){
if (l>r) return (node){0,0,0};
int i,k; ll ans=0; bool u=0,v=0;
for (i=l; i<=r; i++) b[i]=a[i];
while (1){
for (i=k=l; i<=r; i++) if (b[i]>b[k]) k=i;
if (b[k]<=0) return (node){ans,u,v};
if (k==l) u=1; if (k==r) v=1;
ans+=b[k]; b[k-1]=b[k]=b[k+1]=0;
}
}
node mrg(node x,node y){
return (node){x.ans+y.ans,x.u,y.v};
}
void mrg(int k,int l,int r){
int i,j,mid=l+r>>1;
for (i=0; i<2; i++)
for (j=0; j<2; j++)
if (a[mid]>=a[mid+1])
T[k][i][j]=mrg(T[k<<1][i][0],T[k<<1|1][T[k<<1][i][0].v][j]);
else
T[k][i][j]=mrg(T[k<<1][i][T[k<<1|1][0][j].u],T[k<<1|1][0][j]);
}
void build(int k,int l,int r){
if (r-l<=5){
int i,j;
for (i=0; i<2; i++)
for (j=0; j<2; j++) T[k][i][j]=solve(l+i,r-j);
return;
}
int mid=l+r>>1;
build(k<<1,l,mid); build(k<<1|1,mid+1,r);
mrg(k,l,r);
}
void mdy(int k,int l,int r,int x){
if (r-l<=5){
int i,j;
for (i=0; i<2; i++)
for (j=0; j<2; j++) T[k][i][j]=solve(l+i,r-j);
return;
}
int mid=l+r>>1;
if (x<=mid) mdy(k<<1,l,mid,x); else mdy(k<<1|1,mid+1,r,x);
mrg(k,l,r);
}
int main(){
scanf("%d",&n);
int i,x,y;
for (i=1; i<=n; i++) scanf("%d",&a[i]);
build(1,1,n);
scanf("%d",&m);
while (m--){
scanf("%d%d",&x,&y);
a[x]=y; mdy(1,1,n,x);
printf("%lld\n",T[1][0][0].ans);
}
return 0;
}