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

Sample Output

81
88
87

Author
zimpha

Source
2016 Multi-University Training Contest 2

题意：

    维护数组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 ;

 }