Glad You Came（线段树||ST表）

2018-08-09

Glad You Came

题意

不晓得咋说……反正就是把m个区间对应m个vi，对于每一个区间的数字，小于vi的都变成vi，最后求最终结果的i*a[i]的异或。

1、线段树：肯定要维护一个最小值，而且这题由于初始的ai都是0，因此min也是0，而且暴力单点更新，我们只需要建一个一维的数组就好了。然后一个update函数，一个最终结果的计算函数，注意剪枝：” $if(tree[index].val>=v) return “$。

2、反向ST表：我的理解是，对于一个区间$dp[i][d]$，表示的是从i位置开始长度为$2^d$的区间,也就是$[i , i+2^d-1]$。

比如对于区间[1,10]，长度为10，那么我们找到最大的那个<10的$2^d$，即8，d=3，可将区间分成两个：[1,8],[3,10]，用dp[],[]表示就是$dp[1][3]$和$dp[10-2^3+1][3]$。这样对于每一次询问L,R，从一个大区间分出来的两个小区间，维护他们的max值，取max(dp ,val ) 。这样，我们就从最大的区间开始往小了维护，直到$dp[i][0]$这样。

看！代码

/*线段树莽过的做法*/
#include <bits/stdc++.h>
#define MAXN 100010
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned int uint;

long long tree[MAXN<<2];//一定要开到4倍多的空间
int cnt;
long long ans;

uint mod=1<<30;
uint fx(uint &x,uint &y,uint &z)
{
    x=x^(x<<11);
    x=x^(x>>4);
    x=x^(x<<5);
    x=x^(x>>14);
    uint w=x^(y^z);
    x=y;
    y=z;
    z=w;
    return z;
}

int L,R;
long long v;
void update(int l,int r,int index)
{
    if(tree[index]>=v)
        return;
    if(l==r&&tree[index]<v)
    {
        tree[index]=v;
        return ;
    }
    int mid=l+r>>1;
    if(L<=mid)update(l,mid,index<<1);
    if(R>mid)update(mid+1,r,index<<1|1);

    tree[index]=min(tree[index<<1],tree[index<<1|1]);
}
long long cal(int l,int r,int index)
{
    if(l==r)
        return tree[index];
    int mid=l+r>>1;
    if(cnt<=mid)
        return cal(l,mid,index<<1);
    else
        return cal(mid+1,r,index<<1|1);

}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(tree,0,sizeof(tree));
        int n,m;
        cnt=1;
        long long ans=0;
        scanf("%d%d",&n,&m);
        uint x,y,z;
        scanf("%u%u%u",&x,&y,&z);
        for(int i=1;i<=m;i++)
        {
            L=fx(x,y,z)%n+1;
            R=fx(x,y,z)%n+1;
            v=fx(x,y,z)%mod;
            if(L>R) swap(L,R);
            update(1,n,1);
        }
        for(cnt=1;cnt<=n;cnt++)
            ans=ans^(cnt*cal(1,n,1));
        printf("%lld\n",ans);
    }
    return 0;
}

#include <bits/stdc++.h>
#define MAXN 100010
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned int uint;
uint f[15000010];
uint mod=1<<30;
uint fx(uint &x,uint &y,uint &z)
{
    x=x^(x<<11);
    x=x^(x>>4);
    x=x^(x<<5);
    x=x^(x>>14);
    uint w=x^(y^z);
    x=y;
    y=z;
    z=w;
    return z;
}

int l[5000010],r[5000010];
long long v[5000010];
long long dp[100010][18];
int lg[100010];
int main()
{
    int t;
    for(int i=1;i<=100000;i++) lg[i]=log2(i);
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        uint x,y,z;
        scanf("%u%u%u",&x,&y,&z);
        for(int i=1;i<=3*m;i++)
            f[i]=fx(x,y,z);
        for(int i=1;i<=m;i++)
        {
            l[i]=min(f[i*3-2]%n+1,f[i*3-1]%n+1);
            r[i]=max(f[i*3-2]%n+1,f[i*3-1]%n+1);
            v[i]=f[i*3]%mod;
        }
        memset(dp,0,sizeof(dp));
        int d,MAX=-1;
        for(int i=1;i<=m;i++)
        {
            d=lg[r[i]-l[i]+1];
            MAX=max(MAX,d);//记录最长的长度
            dp[l[i]][d]=max(v[i],dp[l[i]][d]); //分为两部分，每一部分取覆盖的最小值和v比较
            dp[r[i]-(1<<d)+1][d]=max(v[i],dp[r[i]-(1<<d)+1][d]);
        }
        for(int j=MAX;j>0;j--)
        {
            for(int i=1;i+(1<<j)-1<=n;i++)
            {
                dp[i][j-1]=max(dp[i][j],dp[i][j-1]);
                dp[i+(1<<(j-1))][j-1]=max(dp[i][j],dp[i+(1<<(j-1))][j-1]);
            }
        }
        long long ans=0;
        for(int i=1;i<=n;i++)
            ans=ans^(1ll*i*dp[i][0]);
        printf("%lld\n",ans);
    }
    return 0;
}