2020-08-03

http://icpc.upc.edu.cn/problem.php?cid=1461&pid=2

题目描述

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同
K=2，读入l,r表示询问l~r之间能见到多少种树
（l,r>0）

输入

第一行n,m表示道路总长为n，共有m个操作
接下来m行为m个操作

输出

对于每个k=2输出一个答案

样例输入

5 4
1 1 3
2 2 5
1 2 4
2 3 5

样例输出’

1
2

提示

20%的数据保证，n,m<=100
60%的数据保证，n <=1000,m<=50000
100%的数据保证，n,m<=50000
采用括号序列+树状数组来解决这道题目，种树为一个区间，我们可以在种树的起点标记一个左括号，种树的终点标记一个右括号，统计的时候计算终点前左括号的数目和起点前右括号的数目，两个做差即为答案。

#include
using namespace std;
typedef long long ll;
ll c1[500500]={0};
ll c2[500500]={0};
ll n,m;
ll lowbit(ll x)
{
    return x&(-x);
}
ll update1(ll k,ll x)
{
    for(ll i=k;i<=n;i+=lowbit(i))
        c1[i]+=x;
}
ll update2(ll k,ll x)
{
    for(ll i=k;i<=n;i+=lowbit(i))
        c2[i]+=x;
}
ll sum1(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c1[i];
    return ans;
}
ll sum2(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c2[i];
    return ans;
}
int main()
{
    ll a,b,c;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++)
    {
       scanf("%lld%lld%lld",&a,&b,&c);
       if(a==1)
       {
           update1(b,1);  /// 左括号
           update2(c,1);  /// 右括号
       }
       else
       {
           printf("%lldn",sum1(c)-sum2(b-1));
       }
    }
}

http://icpc.upc.edu.cn/problem.php?cid=1461&pid=4

题目描述

有一个n个元素的数组，每个元素初始均为0。有m条指令，要么让其中一段连续序列数字反转——0变1，1变0（操作1），要么询问某个元素的值（操作2）。
例如当n=20时，10条指令如下：

输入

第一行包含两个整数n,m，表示数组的长度和指令的条数；
以下m行，每行的第一个数t表示操作的种类：
若t=1，则接下来有两个数L,R，表示区间[L,R]的每个数均反转；
若t=2，则接下来只有一个数i，表示询问的下标。

输出

每个操作2输出一行（非0即1），表示每次操作2的回答。

样例输入

20 10
1 1 10
2 6
2 12
1 5 12
2 6
2 15
1 6 16
1 11 17
2 12
2 6

样例输出

1
0
0
0
1
1

提示

对于50%的数据，1≤n≤103,1≤m≤104；
对于100%的数据，1≤n≤105,1≤m≤5×105，保证L≤R。
与上一道题目同，树状数组统计反转次数即可。

#include
using namespace std;
typedef long long ll;
ll c1[500500]={0};
ll c2[500500]={0};
ll p[500500]={0};
ll n,m;
ll lowbit(ll x)
{
    return x&(-x);
}
ll update1(ll k,ll x)
{
    for(ll i=k;i<=n;i+=lowbit(i))
        c1[i]+=x;
}
ll update2(ll k,ll x)
{
    for(ll i=k;i<=n;i+=lowbit(i))
        c2[i]+=x;
}
ll sum1(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c1[i];
    return ans;
}
ll sum2(ll k)
{
    ll ans=0;
    for(ll i=k;i>=1;i-=lowbit(i))
        ans+=c2[i];
    return ans;
}
int main()
{
    ll a,b,c;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++)
    {
       scanf("%lld",&a);
       if(a==1)
       {
           scanf("%lld%lld",&b,&c);
           update1(b,1);  /// 左括号
           update2(c,1);  /// 右括号
       }
       else
       {
           scanf("%lld",&b);
           printf("%lldn",(sum1(b)-sum2(b-1))%2);
       }
    }
}

http://icpc.upc.edu.cn/problem.php?cid=1431&pid=12

题目描述

在给定的N个整数A1，A2……AN中选出两个进行xor运算，得到的结果最大是多少？

输入

第一行一个整数N，第二行N个整数A1～AN。

输出

一个整数表示答案。

样例输入

3
1 2 3

样例输出

3

提示

对于100%的数据: N<=10^5, 0<=Ai<2^31。
用字典树存二进制，找最大的异或值。

#include 
#include 
using namespace std;
typedef long long ll;
int a[1005000]={0};
int tree[5000500][3]={0};
int tot=1;///必须从1开始
int in(int x)
{
    int p=1;
    for(int i=30;i>=0;i--)
    {
        int k=x>>i&1;
        if(tree[p][k]==0)
            tree[p][k]=++tot;
        p=tree[p][k];
    }
}
int out(int x)
{
    int p=1,ans=0;
    for(int i=30;i>=0;i--)
    {
        int k=x>>i&1;
        if(tree[p][!k])
        {
            ans=ans*2+!k;
            p=tree[p][!k];
        }
        else
        {
            ans=ans*2+k;
            p=tree[p][k];
        }
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    int max1=0;
    for(int i=1;i<=n;i++)
    {
       in(a[i]);
       int num=out(a[i]);
       max1=max(max1,num^a[i]);
    }
    cout<<max1<<endl;
    return 0;
}