P3793 由乃救爷爷

题目背景

大家看过葫芦娃吧？

没看过也没关系，让由乃告诉你吧

传说明斯克航空航天局里关着两个坦克，strv103b和krv。

鼠爷不小心打破了明斯克航空航天局，两个坦克逃了出来，从此其他坦克过上了水深火热的生活。

明斯克航空航天局急忙去告诉一个叫做serb的光头，只有YY出七辆图纸车，才能消灭这两个卖头势力。

serbYY出了七个连图纸都没有的车，却被瑞典人从bbs中窥见 。他们摧毁不了这七个YY车，

就把serb和鼠爷抓去。但是这时候七个坦克模型已经建出来了。

她们分别是 T28原型，T100lt，907工程，蟋蟀15，WZ111，FV215b183，FV215b

她们为了消灭卖头势力，救出serb和鼠爷，一个接一个去与卖头势力搏斗。

T28原是正面很硬的TD，但装甲在金币弹面前一点用都没有，直接被krv卖头打死。

T100lt是隐蔽超好的眼车，却因为没有视野，被103b活活黑死。

907工程是铁头，被krv顶牛直接抽包抽死。

蟋蟀15会黑枪，却因为辣鸡的转向被krv绕死。

WZ111有三百穿，被103b穿侧面一发爆了弹药架。

FV215b183有183炮，103b和krv瑟瑟发抖，不敢打她，于是她解救了其他所有坦克。

但是自己的兄弟FV215b因为瑞典人的诱惑，决定叛变（因为183OO大），TK了183一发，然后183着火烧死了，结果所有坦克都被103b和krv降服了。

瑞典人把七个坦克还有鼠爷一起给serb，让serb做出两辆最强坦克加入瑞典阵营。serb用尽了他所有的脑洞，做出了两辆车E100WT和T-50-2

krv和103b看到之后蛤蛤大笑

krv：E100WT，10mm的脸，不被HE糊死才怪

103b：E100WT，灯塔般的隐蔽，不被黑死才怪

krv：T-50-2，这血量，我一炮就可以打死

103b：T-50-2，看是你机动好还是我黑枪准

serb：百运，胶水，让她们看看你们的厉害

题目描述

故事还没讲完

krv骑坡卖头，却发现百运凭借优秀的精度炮炮打穿她的观察孔

krv慌了，跑去城市里面伸缩，被百运站桩撸死

strv103b跑去草后黑枪，看见胶水在肉侦，却发现自己根本打不中她，然后就被胶水点亮了，百运一梭子128的ARCR飞了过来

strv103b怂了，准备跑路了，但是还没等到自己切换回行走模式，胶水已经开始断她的腿了，被胶水断死

瑞典车们高呼不可战胜，从此不敢嚣张了

然后serb把百运和胶水加入了WOT

从此
其他坦克过上了更加水深火热的生活

然而你又不玩WOT，这事情不管你什么事啊

然而yql是大家的妹妹，所以这件事很重要：

yql在AK曼哈顿OI，CTSC，APIO之后，开始研究数学题。

由乃在挂了字符串OI，CTSC，APIO之后，开始研究大母神原型。

yql出了个数学题，由乃画出了一个表示大母神的图腾。

然后把这两个合成了一个题：

然而由于未知原因那个题挂掉了。。。

由乃想起来SCOI 2017 电子科技大学出了个卡常的rmq，然后发生了一件很有趣的事情

就是一位姓王的同学凭借奇奇怪怪的常数优化怒草了那个题，还比标程块了233倍

所以由乃也出了个卡常rmq，因为没题出了

输入格式

给你一个随机数生成器

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

读入三个数 $n,m,s$

你需要 srand(s) 一下

然后 $n$ 个数表示 $a_i$，这个直接调用 read 函数

然后 $m$ 个询问，表示区间最大值，询问的区间是 $l=\text{read()}\mathrm{mod}n+1,r=\text{read()}\mathrm{mod}n+1$，注意有可能 $l>r$

输出格式

输出一个 unsigned long long 表示每次询问的答案的和

输入输出样例 #1

输入 #1

233 233 233

输出 #1

243704637294

说明/提示

测试点编号	$n,m=$	时限
$1\sim 2$	$1000$	1s
$3$	$10^5$	1s
$4$	$5\times 10^5$	1s
$5$	$10^6$	1s
$6$	$10^7$	5s
$7$	$1.2\times 10^7$	5s
$8$	$1.5\times 10^7$	5s
$9$	$2\times 10^7$	5s

思路

直接暴力即可。

代码

#include<bits/stdc++.h>
#define mae(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
inline void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
inline unsigned read()
{
    using namespace GenHelper;
    unsigned a=rand_()&32767;
    unsigned b=rand_()&32767;
    return a*32768+b;
}
unsigned n,m,s,a[20000007],l,r,ow=0,b[20000007],c[20000007],d[20000007],q,w,e;
unsigned te[80000007];
unsigned long long op=0;
inline void bu(unsigned a1,unsigned l,unsigned r){
	if(l==r){
		te[a1]=a[l];
		return ;
	}
	unsigned mid=(l+r)/2;
	bu(a1*2,l,mid);
	bu(a1*2+1,mid+1,r);
	te[a1]=max(te[a1*2],te[a1*2+1]);
	return ;
}
inline unsigned co(unsigned a1,unsigned l,unsigned r,unsigned x,unsigned y){
	if(x<=l&&r<=y){
		return te[a1];
	}
	unsigned mid=(l+r)/2;
	unsigned dbdb=0;
	if(mid>=x){
		dbdb=max(dbdb,co(a1*2,l,mid,x,y));
	}
	if(mid+1<=y){
		dbdb=max(dbdb,co(a1*2+1,mid+1,r,x,y));
	}
	return dbdb;
}
int main(){
    cin>>n>>m>>s;
    #define nn n
    srand(s);
    for(int i=1;i<=n;++i){
        using namespace GenHelper;
        a[i]=(rand_()&32767)*32768+(rand_()&32767);
    }
    q=n/3;
    w=q*2;
    e=n/2;
    bu(1,1,n);
    if(n<=1000){
        while(m--){
            l=read()%n+1;
            r=read()%n+1;
            if(l>=r){
                swap(l,r);
            }
            op+=co(1,1,n,l,r);
        }
        cout<<op<<endl; 
        return 0;
    }
    q-=1500;
    w+=1500;
    b[q]=a[q];
    for(int i=q-1;i>=1;--i){
        b[i]=mae(b[i+1],a[i]);
    }
    for(int i=q+1;i<=n;++i){
        b[i]=mae(b[i-1],a[i]);
    }
    c[w]=a[w];
    for(int i=w-1;i>=q;--i){
        c[i]=mae(c[i+1],a[i]);
    }
    for(int i=w+1;i<=n;++i){
        c[i]=mae(c[i-1],a[i]);
    }
    d[e]=a[e];
    for(int i=e-1;i>=q;--i){
        d[i]=mae(d[i+1],a[i]);
    }
    for(int i=e+1;i<=w;++i){
        d[i]=mae(d[i-1],a[i]);
    }
    while(m--){
        l=read()%nn+1;
        r=read()%nn+1;
        if(l>=r){
            //swap(l,r);
            if(r<=q){
                if(l>=q){
                    op+=mae(b[r],b[l]);
                }
                else{
                    op+=co(2,1,n/2,r,l);
                }
            }
            else if(r<=w){
                if(l>=w){
                    op+=mae(c[r],c[l]);
                }
                else if(r<=e&&l>=e){
                    op+=mae(d[r],d[l]);
                }
                else{
                    op+=co(1,1,n,r,l);
                }
            }
            else{
                op+=co(3,n/2+1,n,r,l);
            }            
        }
        else{
            if(l<=q){
                if(r>=q){
                    op+=mae(b[l],b[r]);
                }
                else{
                    op+=co(2,1,n/2,l,r);
                }
            }
            else if(l<=w){
                if(r>=w){
                    op+=mae(c[l],c[r]);
                }
                else if(l<=e&&r>=e){
                    op+=mae(d[l],d[r]);
                }
                else{
                    op+=co(1,1,n,l,r);
                }
            }
            else{
                op+=co(3,n/2+1,n,l,r);
            }               
        }
    }
    cout<<op<<endl;
	return 0;
}