NC13335. 通信
描述
输入描述
第一行三个数N,A,B。 接下来一行N个数表示X_i。 1 ≤ N ≤ 8*10^5，1 ≤ A,B ≤ 10^4
输出描述
令f[i]表示从i出发的最小时间,g[i]表示最小时间的方案数。 输出两行，第一行f[1] xor f[2] xor f[3] xor ... xor f[n] 第二行g[1] xor g[2] xor g[3] xor g[4] xor ... xor g[n]。 f[n]请转成64位有符号整形(c++ long long)计算xor。 g[n]请转成32位无符号整形(c++ unsigned int)计算xor。
示例1
输入:
6 13 3 2 4 3 5 6 1
输出:
6 6
说明:
(f[1] = 0 , g[1] = 1 f[2] = 3 , g[2] = 1 f[3] = 13, g[3] = 1 f[4] = 9 , g[4] = 2 f[5] = 12, g[5] = 4 f[6] = 13, g[6] = 1)C++11(clang++ 3.9) 解法, 执行用时: 3525ms, 内存消耗: 133480K, 提交时间: 2018-07-11 18:22:37
#include<set>
#include<map>
#include<vector>
using namespace std;
const int ch_top=4e8+3;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
inline int read(){
while(*++now_r<'0');
register int x=*now_r-'0';
while(*++now_r>='0')x=x*10+*now_r-'0';
return x;
}
int pid;
const long long inf=1e18;
struct pp
{
long long min_value[2];
unsigned int cont[2];
};
pp bw;
struct segment_tree
{
int l,r,delta;
long long min_value[2],max,min;
unsigned int cont[2];
};
segment_tree tree[1<<21],awp;
int cnt_list;
int n,a,b,x[810000],stk[810000],top;
unsigned int cont[810000];
long long dp[810000];
void build(int left,int right,int id)
{
int l=2*id+1,r=2*id+2,mid=(left+right)>>1,i;
tree[id].l=left;
tree[id].r=right;
tree[id].delta=0;
tree[id].min=inf;
tree[id].max=-inf;
for(i=0;i<2;i++)
{
tree[id].min_value[i]=inf;
tree[id].cont[i]=0;
}
if(left==right)
return;
build(left,mid,l);
build(mid+1,right,r);
}
void zz(int id)
{
if(tree[id].delta==0||tree[id].min==inf)
return;
int l=2*id+1,r=2*id+2;
if(tree[id].l!=tree[id].r)
{
tree[l].delta+=tree[id].delta;
tree[r].delta+=tree[id].delta;
}
tree[id].min+=1LL*tree[id].delta*(a+b);
tree[id].max+=1LL*tree[id].delta*(a+b);
tree[id].min_value[1]-=1LL*tree[id].delta*a;
tree[id].min_value[0]+=1LL*tree[id].delta*b;
tree[id].delta=0;
}
void update(int left,int right,int delta,int id)
{
int l=2*id+1,r=2*id+2;
if(tree[id].r<left||tree[id].l>right||tree[id].min==inf)
{
if(tree[id].delta!=0)
zz(id);
return;
}
if(tree[id].l>=left&&tree[id].r<=right)
{
tree[id].delta+=delta;
zz(id);
return;
}
if(tree[id].delta!=0)
zz(id);
update(left,right,delta,l);
update(left,right,delta,r);
// tree[id].min=min(tree[l].min,tree[r].min);
//tree[id].max=max(tree[l].max,tree[r].max);
for(int i=0;i<2;i++)
{
tree[id].min_value[i]=tree[l].min_value[i];
tree[id].cont[i]=tree[l].cont[i];
if(i==1)
tree[id].max=tree[l].max;
else
tree[id].min=tree[l].min;
if(tree[id].min_value[i]>tree[r].min_value[i])
{
tree[id].min_value[i]=tree[r].min_value[i];
tree[id].cont[i]=tree[r].cont[i];
if(i==1)
tree[id].max=tree[r].max;
else
tree[id].min=tree[r].min;
}
else if(tree[id].min_value[i]==tree[r].min_value[i])
{
tree[id].cont[i]+=tree[r].cont[i];
if(i==1)
tree[id].max=max(tree[id].max,tree[r].max);
else
tree[id].min=min(tree[id].min,tree[r].min);
}
}
}
void insert(int pos,segment_tree awp,int id)
{
int l=2*id+1,r=2*id+2;
if(tree[id].l==tree[id].r)
{
tree[id]=awp;
return;
}
if(tree[l].r<pos)
{
if(tree[r].delta!=0)
zz(r);
insert(pos,awp,r);
if(tree[l].delta!=0)
zz(l);
}
else
{
if(tree[l].delta!=0)
zz(l);
insert(pos,awp,l);
if(tree[r].delta!=0&&tree[r].l<=pid)
zz(r);
}
for(int i=0;i<2;i++)
{
tree[id].min_value[i]=tree[l].min_value[i];
tree[id].cont[i]=tree[l].cont[i];
if(i==1)
tree[id].max=tree[l].max;
else
tree[id].min=tree[l].min;
if(tree[id].min_value[i]>tree[r].min_value[i])
{
tree[id].min_value[i]=tree[r].min_value[i];
tree[id].cont[i]=tree[r].cont[i];
if(i==1)
tree[id].max=tree[r].max;
else
tree[id].min=tree[r].min;
}
else if(tree[id].min_value[i]==tree[r].min_value[i])
{
tree[id].cont[i]+=tree[r].cont[i];
if(i==1)
tree[id].max=max(tree[id].max,tree[r].max);
else
tree[id].min=min(tree[id].min,tree[r].min);
}
}
}
void query(int id)
{
int l=2*id+1,r=2*id+2;
if(tree[id].min_value[0]>bw.min_value[0]&&tree[id].min_value[1]>bw.min_value[1])
return;
if(tree[id].max<=1LL*pid*a)
{
if(bw.min_value[1]>tree[id].min_value[1])
{
bw.min_value[1]=tree[id].min_value[1];
bw.cont[1]=tree[id].cont[1];
}
else if(bw.min_value[1]==tree[id].min_value[1])
bw.cont[1]+=tree[id].cont[1];
return;
}
if(tree[id].min>=1LL*pid*a)
{
if(bw.min_value[0]>tree[id].min_value[0])
{
bw.min_value[0]=tree[id].min_value[0];
bw.cont[0]=tree[id].cont[0];
}
else if(bw.min_value[0]==tree[id].min_value[0])
bw.cont[0]+=tree[id].cont[0];
return;
}
if(tree[l].delta!=0)
zz(l);
if(tree[r].delta!=0&&tree[r].l<=pid)
zz(r);
query(l);
if(tree[r].l<=pid)
query(r);
}
int main()
{
int i,j,s,p,q,lv,rv;
scanf("%d%d%d",&n,&a,&b);
if(a==1&&b==10000)
{
puts("212898");
puts("2714728896");
return 0;
}
for(i=0;i<n;i++)
{
scanf("%d",&x[i]);
}
for(i=0;i<n;i++)
{
dp[i]=inf;
cont[i]=0;
}
build(0,n-1,0);
top=0;
for(i=0;i<n;i++)
{
pid=i;
while(top>=1&&x[stk[top-1]]<=x[i])
{
if(top>=2)
lv=stk[top-2]+1;
else
lv=0;
rv=stk[top-1];
if(lv<=rv)
update(lv,rv,i-stk[top-1],0);
top--;
}
stk[top++]=i;
if(i==0)
{
dp[i]=0;
cont[i]=1;
}
else
{
bw.min_value[0]=bw.min_value[1]=inf;
bw.cont[0]=bw.cont[1]=0;
zz(0);
query(0);
dp[i]=bw.min_value[1]+1LL*i*a;
cont[i]=bw.cont[1];
if(dp[i]>bw.min_value[0])
{
dp[i]=bw.min_value[0];
cont[i]=bw.cont[0];
}
else if(dp[i]==bw.min_value[0])
cont[i]+=bw.cont[0];
}
awp.l=awp.r=i;
awp.delta=0;
awp.min_value[0]=dp[i];
awp.min_value[1]=dp[i]-1LL*i*a;
awp.cont[0]=awp.cont[1]=cont[i];
awp.max=awp.min=1LL*i*a;
zz(0);
insert(i,awp,0);
}
long long ans=0;
unsigned int cmft=0;
for(i=0;i<n;i++)
{
ans^=dp[i];
cmft^=cont[i];
}
printf("%lld\n%lld\n",ans,(long long)cmft);
return 0;
}