首页 > 其他 > 详细

hdu 6319 逆序建单调队列

时间:2019-09-23 01:10:26      阅读:168      评论:0      收藏:0      [点我收藏+]

题目传送门//res tp hdu

维护递增单调队列
根据数据范围推测应为O(n)的.
我们需要维护一个区间的信息,区间内信息是“有序”的,同时需要在O(1)的时间进行相邻区间的信息转移.
若是主数列从头到尾转移无法有解题突破口,就反过来从尾到头再思考.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i = (a);i>=(b);--i)
#define fo(i,a,b) for(int i =(a);i<(b);++i)
#define de(x) cout<<#x<<" = "<<x<<endl;
#define endl '\n'
#define ls(p) ((p)<<1)
#define rs(p) (((p)<<1)|1)
using namespace std;
typedef long long ll;
const int mn = 1e7+10;
int T;
ll a[mn];
ll n,m,k,p,q,r,MOD;
int L,R;
int tmaxr;
ll A,B;
ll val[mn];
int pos[mn];
int main(){
    scanf("%d",&T);
    while(T--){
        A = B = 0;
        scanf("%lld %lld %lld %lld %lld %lld %lld",&n,&m,&k,&p,&q,&r,&MOD);
        rep(i,1,k)  scanf("%lld",&a[i]);
        if(k<n)
        rep(i,k+1,n) a[i] = (p*a[i-1]+q*i+r)%MOD;
        L = R = n-m+1;
        val[L] = a[L]; pos[L] = L;
        tmaxr = a[L];
        int tem = n-m+2;
        rep(i,tem,n) if(a[i] > tmaxr){
            ++R;
            val[R] = a[i]; pos[R]=i;
            tmaxr = a[i];
        }
        A += L^tmaxr;
        B += L^(R-L+1);
        tem-=2;
        per(i,tem,1){
            while(L<=R&&pos[R] > i + m - 1){
                    R--;
            }
            if(a[i] >= a[i+1]){
                while(L<=R&&val[L] <= a[i]){
                    L++;
                }
            }
            L--;
            val[L]=a[i];pos[L]=i;
            A += val[R]^i;
            B += (R - L + 1)^i;
        }
        printf("%lld %lld\n",A,B);
    }
}

hdu 6319 逆序建单调队列

原文:https://www.cnblogs.com/tea-egg/p/11569943.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!