注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3745][Coci2015]Norma  

2015-01-27 20:38:30|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3745: [Coci2015]Norma

倒是不难想但是写起来异常恶心QAQ
写了差不多一天……细节方面真是太感人了
这是我第一道写到一半被恶心得先去写了暴力和数据生成器的题
不过其实觉得恶心应该是智商不够……
不过Rank1了还是蛮开心
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1E9;
const int N = 5E5+10;
int scan(){
char cc=' ';int re=0,fh=1;while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){re=re*10+cc-'0';cc=getchar();}return re*fh;
}
int n,m,data[N],ans,ln[2];
struct Node{Node(int aa=0,int bb=0,int cc=0){i=aa;d1=bb;d2=cc;}int i,d1,d2;}list[2][N];
struct Que{
//dui[0] -> get min
//dui[1] -> get max
deque<Node>dui[2];
int tmp,ans;
Que(){dui[0].push_back(Node());dui[1].push_back(Node());}
bool better(int a,int b,int t){
if(!t) return data[a] >= data[b];
else return data[a] <= data[b];
}
Node sum(int x,int t){
int l=0,r=dui[t].size()-1;
while(l<r){
int mid = (l+r)/2;
if(dui[t][mid].i == x)return dui[t][mid];
if(dui[t][mid].i > x)r = mid;
else l = mid+1;
}
Node re = dui[t][l];
re.d2 = (re.d2 - (ll)(x+1 + re.i)*(re.i - x )/2%MOD * data[re.i])%MOD;
re.d1 = (re.d1 - (ll)(re.i - x )*data[re.i]) %MOD;
return re;
}
void pop(int x,int t){
ln[t] = 0;
while(dui[t].size() > 1 && better(dui[t].back().i,x,t)){
list[t][++ln[t]] = dui[t].back();
dui[t].pop_back();
}
list[t][++ln[t]] = dui[t].back();
}
void push(int x){
int i,j,last[2],lastp = x-1,val,len,t,p;
//part 1 - sub the same part
last[0] = data[list[0][1].i];last[1] = data[list[1][1].i];

if(x == 3)
x=3;
//(this , last]
for(i = j = 2;i<=ln[0]&&j<=ln[1];){
val = (ll)last[0]*last[1]%MOD;
if(list[0][i].i > list[1][j].i){
p = list[0][i].i;
len = lastp - p;
ans = (ans - (ll)(((x-1) - (lastp)+1) + ((x-1) - (p+1)+1))*len/2%MOD * val)%MOD;
tmp = (tmp - (ll)len*val)%MOD;
lastp = p;
last[0] = data[p];
i++;
}else{
p = list[1][j].i;
len = lastp - p;
ans = (ans - (ll)(((x-1) - (lastp)+1) + ((x-1) - (p+1)+1))*len/2%MOD * val)%MOD;
tmp = (tmp - (ll)len*val)%MOD;
lastp = p;
last[1] = data[p];
j++;
}
}
//part 2 - sub the special part
t = 0;if(i>ln[0])swap(i,j),t=1;
j = i;
Node ntmp[2];
for(;i<=ln[t];i++){
p = list[t][i].i;
ntmp[1] = sum(lastp,t^1);
ntmp[0] = sum(p,t^1);
ntmp[1].d1 = (ntmp[1].d1 - ntmp[0].d1)%MOD;
ntmp[1].d2 = (ntmp[1].d2 - ntmp[0].d2)%MOD;
ntmp[1].d2 = ((ll)ntmp[1].d1*(lastp+1) - ntmp[1].d2 + (ll)ntmp[1].d1*((x-1) - lastp) )%MOD;
ans = (ans - (ll)last[t]*ntmp[1].d2)%MOD;
tmp = (tmp - (ll)last[t]*ntmp[1].d1)%MOD;
ans = (ans + (ll)data[x]*ntmp[1].d2)%MOD;
tmp = (tmp + (ll)data[x]*ntmp[1].d1)%MOD;
lastp = p;last[t] = data[p];
}
//part 3 - add the special part
/*
ntmp[0] = sum(lastp,t^1);
ntmp[1] = sum(dui[t^1].back().i,t^1);
ntmp[1].d1 = (ntmp[1].d1 - ntmp[0].d1)%MOD;
ntmp[1].d2 = (ntmp[1].d2 - ntmp[0].d2)%MOD;
*/
//part 4 - add the same part
val = (ll)data[x]*data[x]%MOD;
p = max(dui[0].back().i,dui[1].back().i)+1;
len = (x-1)-p+1;
ans = (ans + (1+len)*len/2%MOD * val)%MOD;
tmp = (tmp + (ll)val*len)%MOD;
//part 5 - update final ans
tmp = (tmp + (ll)data[x]*data[x])%MOD;
ans = (ans + tmp)%MOD;
//part 6 - push new
len = x - dui[0].back().i;Node now;
now = dui[0].back();now.i = x;
now.d1 = (now.d1 + (ll)data[x]*len)%MOD;
now.d2 = (now.d2 + (ll)len*(x + dui[0].back().i+1)/2%MOD * data[x])%MOD;
dui[0].push_back(now);
len = x - dui[1].back().i;
now = dui[1].back();now.i = x;
now.d1 = (now.d1 + (ll)data[x]*len)%MOD;
now.d2 = (now.d2 + (ll)len*(x + dui[1].back().i+1)/2%MOD * data[x])%MOD;
dui[1].push_back(now);
}
void print();
}que;
void Que::print(){
int i,j;
printf("Dui[0]: ");
for(i=0;i<dui[0].size();i++){
printf("{%d %d %d} ",data[dui[0][i].i],dui[0][i].d1,dui[0][i].d2);
}printf("\n");
printf("Dui[1]: ");
for(i=0;i<dui[1].size();i++){
printf("{%d %d %d} ",data[dui[1][i].i],dui[1][i].d1,dui[1][i].d2);
}printf("\n");
printf("%d %d\n\n",tmp,ans);
}
int main(){
freopen("in.txt","r",stdin);
int i,j;
n = scan();for(i=1;i<=n;i++)data[i] = scan();
for(i=1;i<=n;i++){
que.pop(i,0);que.pop(i,1);
que.push(i);
ans += que.ans;
if(ans >= MOD)ans-=MOD;
//que.print();
}
if(ans < 0)ans += MOD;
printf("%d\n",ans);
return 0;
}

题解:
求sigma[所有区间l,r](r-l+1)*min*max
单调队列(其实单调栈也可以)+二分
由于被恶心到了所以我直接贴一下我写的时候整理的东西好了。。。

倒序扫描维护两个单调队列,

两个单调队列分别是最大值/最小值

队列的每个位置顺便维护
前缀和 p[i] * i 和 前缀和p[i]

然后每次剔除队尾值的时候
先把两队都要踢的部分拿出来
暴力扫一遍,ans - 这部分答案 | tmp - Sum
某一部分多踢的一段: 每次多踢一个二分一次
ans - 这部分答案( [p[i]*?] - [p[i]*i] )*? | tmp - Sum

更新
先加多踢的那部分
ans + ( [] - [] )*? | tmp + Sum
再加一起踢的部分
ans +
最后加新加的部分
tmp + d*d

更新答案:
ans + tmp
更新队列维护的两个东西

最后ans+=this time
有点类似树状数组维护区间加区间查询

大概就是说以i为右边界的所有区间的答案是******
我不会说了……以样例中i=3为例吧
这次的答案是 
2 4 1
(4*1)*3 + (4*1)*2 + (1*1)*1 = 21
然后我们上面说的tmp = (4*1) + (4*1) + (1*1)
  评论这张
 
阅读(118)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017