Differencia
Time Limit: 10000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 601 Accepted Submission(s): 173
Problem Description
Professor Zhang has two sequences a1,a2,...,an and b1,b2,...,bn. He wants to perform two kinds of operations on the sequences:
1. + l r x: set ai to x for all l≤i≤r.
2. ? l r: find the number of i such that ai≥bi and l≤i≤r.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains four integers n, m, A and B (1≤n≤105,1≤m≤3000000,1≤A,B≤216) -- the length of the sequence, the number of operations and two parameters.
The second line contains n integers a1,a2,...,an (1≤ai≤109). The third line contains n integers b1,b2,...,bn (1≤bi≤109).
As there are too many operations, the m operations are specified by parameters A and B given to the following generator routine.
int a = A, b = B, 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;
}
For the i-th operation, first call rnd(last) three times to get l, r and x (i.e. l = rnd(last) % n + 1, r = rnd(last) % n + 1, x = rnd(last) + 1). Then if l>r, you should swap their value. And at last, the i-th operation is type ?, if (l+r+x) is an even number, or type + otherwise.
Note: last is the answer of the latest type ? operation and assume last=0 at the beginning of each test case.
Output
For each test case, output an integer S=(∑i=1mi⋅zi) mod (109+7), where zi is the answer for i-the query. If the i-th query is of type +, then zi=0.
Sample Input
3
5 10 1 2
5 4 3 2 1
1 2 3 4 5
5 10 3 4
5 4 4 2 1
1 2 3 4 5
5 10 5 6
5 4 5 2 1
1 2 2 4 5
5 10 1 2
5 4 3 2 1
1 2 3 4 5
5 10 3 4
5 4 4 2 1
1 2 3 4 5
5 10 5 6
5 4 5 2 1
1 2 2 4 5
Sample Output
81
88
87
88
87
Author
zimpha
Source
题意：
维护数组a，两种操作：
1、l～r全部赋值为x
2、l～r查询满足a[i]>=b[i]的i有多少个。
题解：
其实官方题解已经很清楚了：
这道题O(nlog2n)的线段树套有序表做法很显然.
线段树每个节点[l,r]维护这个区间内, 数组bb排序好的结果.
然后对于修改操作, 只要在这个区间内二分一下就能知道这个区间的答案
(往子节点标记时也同理).
这个做法常数很小, 跑的很快, 但是应该被卡了
(没测过zkw写法, 也许能过), 理由参考第一句话. 上面方法稍作修改就可以得到一个O(nlogn)的做法,
除了有序表线段树每个节点同时维护有序表第ii个数进入左右子树时的位置.
那么只要在线段树根节点做一次二分,
之后就可以O(1)查询这个数在左右子树的rank变化.
这个对线段树往下push lazy标记也是适用的. 本质就是归并树。
假设现在对于修改操作，对于某个节点的有序表，我知道前k个满足b[i]<=x
那么只要预处理出到i位置，这前i个，有lsh个进入左子树，rsh进入右子树。
那么对于左子树，它的有序表前lsh全是满足b[i]<=x的。
同理，右子树的有序表前rsh个也是满足b[i]<=x的。
这样我们只用二分一次，接下来就能推出子树所有的情况了。
当遇到目标区间是，就知道这个区间有k‘个满足b[i]<=x了
这个k'是父亲直接传下来的（是lsh或者rsh）。
然后直接打懒惰标记好了。
询问就是求和操作。
const int N = , M = , MOD = 1e9 + ;
struct MergeTree {
static struct Node {
static int tot;
int child[], cnt;
bool tag;
int lside; inline void init() {
child[] = child[] = -, cnt = lside = , tag = false;
}
} tr[N * M];
static int tol[N * M], len; #define child(x, y) tr[x].child[y]
#define lc(x) child(x, 0)
#define rc(x) child(x, 1)
#define cnt(x) tr[x].cnt
#define tag(x) tr[x].tag
#define lside(x) tr[x].lside
#define tol(x, y) (y ? tol[lside(x) + y - 1] : 0)
#define tor(x, y) (y ? y - tol[lside(x) + y - 1] : 0) inline static void init() {
Node::tot = , len = ;
} inline static void pushdown(int x) {
if(tag(x)) {
tag(lc(x)) = tag(rc(x)) = true, tag(x) = false;
cnt(lc(x)) = tol(x, cnt(x)), cnt(rc(x)) = tor(x, cnt(x));
}
} inline static void updata(int x) {
cnt(x) = ;
for(int i = ; i < ; ++i) cnt(x) += cnt(child(x, i));
} inline static void build(int &x, int l, int r, int a[], int b[]) {
static int tmp[N];
if(x < ) tr[x = Node::tot++].init();
if(l >= r) cnt(x) = (a[l] >= b[l]);
else {
int mid = (l + r) >> ;
build(lc(x), l, mid, a, b), build(rc(x), mid + , r, a, b);
updata(x); int indexL = l, indexR = mid + , now = l;
lside(x) = len;
while(indexL <= mid && indexR <= r) {
if(len > lside(x)) tol[len] = tol[len - ];
else tol[len] = ;
if(b[indexL] <= b[indexR])
++tol[len], tmp[now++] = b[indexL++];
else tmp[now++] = b[indexR++];
++len;
}
while(indexL <= mid) {
tol[len] = tol[len - ] + ;
tmp[now++] = b[indexL++], ++len;
}
while(indexR <= r) {
tol[len] = tol[len - ];
tmp[now++] = b[indexR++], ++len;
}
for(int i = l; i <= r; ++i) b[i] = tmp[i];
}
} inline static int query(int x, int l, int r, int lef, int rig) {
if(rig < l || lef > r) return ;
if(lef <= l && r <= rig) return cnt(x);
int mid = (l + r) >> ;
pushdown(x);
return query(lc(x), l, mid, lef, rig) +
query(rc(x), mid + , r, lef, rig);
} inline static void modify(int x, int l, int r,
int rk, int lef, int rig) {
if(rig < l || lef > r) return;
if(lef <= l && r <= rig) cnt(x) = rk, tag(x) = true;
else {
pushdown(x);
int mid = (l + r) >> ;
modify(lc(x), l, mid, tol(x, rk), lef, rig);
modify(rc(x), mid + , r, tor(x, rk), lef, rig);
updata(x);
}
} #undef child
#undef lc
#undef rc
#undef cnt
#undef tag
#undef lside
#undef tol
#undef tor
};
int MergeTree::Node::tot, MergeTree::tol[N * M], MergeTree::len;
MergeTree::Node MergeTree::tr[N * M];
int n, m, A, B;
int a[N], b[N]; int C = ~( << ), MM = ( << ) - ;
inline int rnd(int last) {
A = ( + (last >> )) * (A & MM) + (A >> );
B = ( + (last >> )) * (B & MM) + (B >> );
return (C & ((A << ) + B)) % ;
} inline void solve() {
MergeTree::init();
int root = -, lst = , ans = ;
MergeTree::build(root, , n - , a, b);
for(int index = ; index <= m; ++index) {
int l = rnd(lst) % n + , r = rnd(lst) % n + , x = rnd(lst) + ;
if(l > r) swap(l, r);
--l, --r;
if((l + r + x) & ) {
int rk = upper_bound(b, b + n, x) - b;
MergeTree::modify(root, , n - , rk, l, r);
} else {
lst = MergeTree::query(root, , n - , l, r);
ans = (ans + index * 1ll * lst) % MOD;
}
} printf("%d\n", ans);
} int main() {
int testCase;
scanf("%d", &testCase);
while(testCase--) {
scanf("%d%d%d%d", &n, &m, &A, &B);
for(int i = ; i < n; ++i) scanf("%d", &a[i]);
for(int i = ; i < n; ++i) scanf("%d", &b[i]);
solve();
}
return ;
}