hdu 5737Differencia题意：思路：代码：

68 阅读 0 评论 45 点赞

我是靠谱客的博主淡然小兔子，最近开发中收集的这篇文章主要介绍hdu 5737Differencia题意：思路：代码：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Differencia

Time Limit: 10000/10000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 997 Accepted Submission(s): 293

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和B数组，有两个操作，第一个操作是将A数组从l到r区间所有数置为x，第二个操作是询问A数组从l到r区间有多少个a[i]>=b[i]的。有m次操作，每次操作都是根据题目给的函数生成出来的。

思路：

对这道题我是没什么思路的，看了其他人的博客，才明白线段树套有序表这么巧妙的组合。在创建线段树的过程中，有序数组就可以创建出来。并且创造出父亲与左右儿子之间的映射关系，有点归并排序的意思。

线段树中创建的有序表是存的B数组，对于第一个操作，我们只需要把sum数组进行更新就行了，每次往下找的时候都是根据之前预处理好的对应关系来向下找到对应的位置，就可以直接更新sum数组。第二个操作就是基本的线段树操作。

代码：

#include <bits/stdc++.h>
#define ls i<<1
#define rs ls|1
#define mid (l + r >> 1)
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int a1[maxn],a2[maxn];
int san[maxn*20],st[maxn*4],ed[maxn*4],sum[maxn*4],down[maxn*4];
int to[2][maxn*20];
int a,b,C,M;
int cnt;
void pushup(int i){sum[i]=sum[ls]+sum[rs];}
void pushdown(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 build(int i,int l,int r)
{
    down[i]=-1;
    san[cnt++]=-inf;
    st[i]=cnt;
    for(int i=l;i<=r;i++) san[cnt++]=a2[i];
    ed[i]=cnt;
    sort(san+st[i],san+ed[i]);
    if(l==r)
    {
        sum[i]=(a1[l]>=a2[l]);
        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;
    pushup(i);
}
void update(int i,int l,int r,int x,int y,int pos)
{
    if(x<=l&&r<=y)
    {
        sum[i]=pos-st[i]+1;
        down[i]=pos;
        return;
    }
    pushdown(i);
    if(x<=mid) update(lson,x,y,to[0][pos]);
    if(y>mid) update(rson,x,y,to[1][pos]);
    pushup(i);
}
int query(int i,int l,int r,int x,int y)
{
    int ans=0;
    if(x<=l&&r<=y) return sum[i];
    pushdown(i);
    if(x<=mid) ans+=query(lson,x,y);
    if(y>mid) ans+=query(rson,x,y);
    pushup(i);
    return ans;
}
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 t,n,m,A,B,x;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        int last=0,ans=0;
        scanf("%d%d%d%d",&n,&m,&a,&b);
        for(int i=1;i<=n;i++) scanf("%d",&a1[i]);
        for(int i=1;i<=n;i++) scanf("%d",&a2[i]);
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            C = ~(1<<31),M = (1<<16)-1;
            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)%2==0)// ?
            {
                last=query(1,1,n,l,r);
                int tmp=((ll)last*i)%mod;
                ans=(ans+tmp)%mod;
            }
            else
            {
                x=upper_bound(san+st[1],san+ed[1],x)-san;
                update(1,1,n,l,r,x-1);
            }
        }
        printf("%dn",ans);
    }
    return 0;
}