【hdu 6319】Ascending Rating

给你一个长为n的数组a
让你对于每个长度为m的窗口。
算出其中的最大值以及从左往右遍历的时候这个最大值更新的次数。

【题解】

单调队列。
从后往前滑动窗口。
会发现我们维护以这个窗口里面的值为元素的单调队列的时候。
这个单调队列的长度就是最大值更新的次数。
因为我们把a[i]加入队列的时候。
队列尾巴上,小于等于这个a[i]的元素都会被删掉.
每个都这么做的话。
队列里面的元素就和更新时候的元素对应。
最大值就是队列的头部。
少做一些取余操作。不然会超时。

【代码】

#include <bits/stdc++.h>

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

using namespace std;

namespace IO {

    const int MX = 4e7;

    char buf[MX]; int c, sz;

    void begin() {

        c = 0;

        sz = fread(buf, 1, MX, stdin);

    }

    inline bool read(int &t) {

        while(c < sz && buf[c] != '-' && (buf[c] < '0' || buf[c] > '9')) c++;

        if(c >= sz) return false;

        bool flag = 0; if(buf[c] == '-') flag = 1, c++;

        for(t = 0; c < sz && '0' <= buf[c] && buf[c] <= '9'; c++) t = t * 10 + buf[c] - '0';

        if(flag) t = -t;

        return true;

    }

}

const int N = 1e7;

int n,m,k,p,q,r,MOD,a[N+10];

int max_queue[N+10],h,t;

int main(){

    //freopen("rush_in.txt", "r", stdin);

    int T;

    IO::begin();

    IO::read(T);

    while(T--){

        IO::read(n);IO::read(m);IO::read(k);IO::read(p);IO::read(q);IO::read(r);IO::read(MOD);

        rep1(i,1,k) IO::read(a[i]);

        rep1(i,k+1,n) a[i] = (1LL*p*a[i-1] + 1LL*q*i+r)%MOD;

        h = 1,t = 0;

        long long A=0,B=0;

        h = 1,t = 0;

        rep2(i,n,1)

        {

            if (i < n-m+1) while ( h<=t && max_queue[h]>i+m-1) h++;

            while (h<= t && a[max_queue[t]]<=a[i]) t--;

            t++;

            max_queue[t] = i;

            if (i <= n-m+1)

                {

                A = A + (a[max_queue[h]]^i);

                B = B + ((t-h+1)^i);

            }

        }

        printf("%lld %lld\n",A,B);

    }

    return 0;

}

巴特西

【hdu 6319】Ascending Rating

最新文章

热门文章