概述
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define LL long long
#define pii pair<int,int>
#define MP make_pair
#define ls i << 1
#define rs ls | 1
#define md (ll + rr >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs
#define Pi acos(-1.0)
#define mod 1000000007
#define eps 1e-12
#define inf 0x3f3f3f3f
#define N 100010
int down[N<<2], san[N*20], A[N], B[N], sum[N<<2];
int st[N<<2], ed[N<<2], to[2][N*20];
int tot, n, m, a, b;
void build(int ll, int rr, int i){
down[i] = -1;
san[tot++] = -inf;
st[i] = tot;
for(int j = ll; j <= rr; ++j){
san[tot++] = B[j];
}
ed[i] = tot;
sort(san + st[i], san + ed[i]);
if(ll == rr){
if(A[ll] >= B[ll]) sum[i] = 1;
else sum[i] = 0;
return ;
}
build(lson);
build(rson);
int lx = st[ls], rx = st[rs];
for(int j = st[i]; j < ed[i]; ++j){
while(lx < ed[ls] && san[lx] <= san[j]) ++lx;
while(rx < ed[rs] && san[rx] <= san[j]) ++rx;
to[0][j] = lx - 1;
to[1][j] = rx - 1;
}
to[0][st[i]-1] = st[ls] - 1;
to[1][st[i]-1] = st[rs] - 1;
sum[i] = sum[ls] + sum[rs];
}
void push_down(int i){
if(~down[i]){
down[ls] = to[0][down[i]];
sum[ls] = down[ls] - st[ls] + 1;
down[rs] = to[1][down[i]];
sum[rs] = down[rs] - st[rs] + 1;
down[i] = -1;
}
}
void update(int l, int r, int x, int ll, int rr, int i){
if(l == ll && r == rr){
sum[i] = x - st[i] + 1;
down[i] = x;
return ;
}
push_down(i);
if(r <= md) update(l, r, to[0][x], lson);
else if(l > md) update(l, r, to[1][x], rson);
else update(l, md, to[0][x], lson), update(md + 1, r, to[1][x], rson);
sum[i] = sum[ls] + sum[rs];
}
int query(int l, int r, int ll, int rr, int i){
if(l == ll && r == rr) return sum[i];
push_down(i);
if(r <= md) return query(l, r, lson);
else if(l > md) return query(l, r, rson);
else return query(l, md, lson) + query(md + 1, r, rson);
}
int C = ~(1<<31), M = (1<<16)-1;
int rnd(int last) {
a = (36969 + (last >> 3)) * (a & M) + (a >> 16);
b = (18000 + (last >> 3)) * (b & M) + (b >> 16);
return (C & ((a << 16) + b)) % 1000000000;
}
int main(){
int cas;
scanf("%d", &cas);
while(cas--){
scanf("%d%d%d%d", &n, &m, &a, &b);
for(int i = 1; i <= n; ++i)
scanf("%d", &A[i]);
for(int i = 1; i <= n; ++i)
scanf("%d", &B[i]);
tot = 0;
build(1, n, 1);
int last = 0, ans = 0;
for(int i = 1; i <= m; ++i){
int l = rnd(last) % n + 1, r = rnd(last) % n + 1, x = rnd(last) + 1;
if(l > r) swap(l, r);
if((l + r + x) & 1){
x = upper_bound(san + st[1], san + ed[1], x) - san;
update(l, r, x - 1, 1, n, 1);
}
else{
last = query(l, r, 1, n, 1);
ans += 1LL * i * last % mod;
if(ans >= mod) ans -= mod;
}
}
printf("%dn", ans);
}
return 0;
}
最后
以上就是陶醉哑铃为你收集整理的hdu 5737(线段树)的全部内容,希望文章能够帮你解决hdu 5737(线段树)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复