FZU 2105 Digits Count

 Problem 2105 Digits Count

Accept: 444    Submit: 2139 Time Limit: 10000 mSec    Memory Limit : 262144 KB

 Problem Description

Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:

Operation 1: AND opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).

Operation 2: OR opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).

Operation 3: XOR opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).

Operation 4: SUM L R

We want to know the result of A[L]+A[L+1]+...+A[R].

Now can you solve this easy problem?

 Input

The first line of the input contains an integer T, indicating the number of test cases. (T≤100)

Then T cases, for any case, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000), indicating the number of elements in A and the number of operations.

Then one line follows n integers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).

Then m lines, each line must be one of the 4 operations above. (0≤opn≤15)

 Output

For each test case and for each "SUM" operation, please output the result with a single line.

 Sample Input

14 41 2 4 7SUM 0 2XOR 5 0 0OR 6 0 3SUM 0 2

 Sample Output

718

 Hint

A = [1 2 4 7]

SUM 0 2, result=1+2+4=7;

XOR 5 0 0, A=[4 2 4 7];

OR 6 0 3, A=[6 6 6 7];

SUM 0 2, result=6+6+6=18.

线段树,由于数组范围只有0到17,所以会有大量重复的块,所以直接线段树暴力来

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

using namespace std;
typedef long long int LL;
const int maxn=1e6;
int num[maxn*4+5];
int sum[maxn*4+5];
int n,m;
void pushup(int node)
{
    sum[node]=sum[node<<1]+sum[node<<1|1];
    if(num[node<<1]==num[node<<1|1]&&num[node<<1]!=-1)
        num[node]=num[node<<1];
    else
        num[node]=-1;
}
void build(int node,int l,int r)
{
    if(l==r)
    {
        scanf("%d",&num[node]);
        sum[node]=num[node];
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    pushup(node);
}
void update(int node,int l,int r,int L,int R,int tag,int flag)
{
    if(L<=l&&r<=R)
    {
        if(num[node]!=-1)
        {
            if(tag==1) num[node]&=flag;
            else if(tag==2) num[node]|=flag;
            else num[node]^=flag;
            sum[node]=num[node]*(r-l+1);
            return;
        }
        int mid=(l+r)>>1;
        if(L<=mid)
            update(node<<1,l,mid,L,R,tag,flag);
        if(R>mid)
            update(node<<1|1,mid+1,r,L,R,tag,flag);
        pushup(node);
        return;
    }
    int mid=(l+r)>>1;
    if(num[node]!=-1)
    {
        sum[node<<1]=num[node]*(mid-l+1);
        sum[node<<1|1]=num[node]*(r-mid);
        num[node<<1]=num[node<<1|1]=num[node];
        
    }


    if(L<=mid) update(node<<1,l,mid,L,R,tag,flag);
    if(R>mid) update(node<<1|1,mid+1,r,L,R,tag,flag);
    pushup(node);
}

int query(int node,int l,int r,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return sum[node];
    }
    int mid=(l+r)>>1;
    if(num[node]!=-1)
    {
        sum[node<<1]=num[node]*(mid-l+1);
        sum[node<<1|1]=num[node]*(r-mid);
        num[node<<1]=num[node<<1|1]=num[node];
        
    }
    int ret=0;
    if(L<=mid) ret+=query(node<<1,l,mid,L,R);
    if(R>mid) ret+=query(node<<1|1,mid+1,r,L,R);
    return ret;
}
int main()
{
    int t;
    scanf("%d",&t);
    char a[10];
    int x,y,z;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(num,-1,sizeof(num));
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            scanf("%s",a);
            if(a[0]=='A')
            {
                scanf("%d%d%d",&x,&y,&z);
                update(1,1,n,y+1,z+1,1,x);
            }
            else if(a[0]=='O')
            {
                scanf("%d%d%d",&x,&y,&z);
                update(1,1,n,y+1,z+1,2,x);
            }
            else if(a[0]=='X')
            {
                scanf("%d%d%d",&x,&y,&z);
                update(1,1,n,y+1,z+1,3,x);
            }
            else
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",query(1,1,n,x+1,y+1));
            }
        }

    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术点滴

Windows注册表操作基础代码

Windows注册表操作基础代码     Windows下对注册表进行操作使用的一段基础代码Reg.h: #pragma once #include<asser...

2149
来自专栏我的博客

Zend Framework自动加载、简单路由配置(Bootstrap.php)

<?php class Bootstrap extends Zend_Application_Bootstrap_Bootstrap { /* * 自动加...

3538
来自专栏醉梦轩

Linux上C语言写的简易telnet客户端

1732
来自专栏闵开慧

hive启动后相关操作

hadoop@ubuntu118:~$ $HIVE_HOME/bin/hive WARNING: org.apache.hadoop.metri...

3578
来自专栏Pulsar-V

OpenCV编译参数一览

全部参数一览 //Path to a program. ANT_EXECUTABLE:FILEPATH=D:/apache-ant-1.10.1/bin/ant...

7996
来自专栏竹清助手

安装MariaDB 无法登录解惑

Debian 9 installed mariadb-server , the phpmyadmin can't login and terminal too,...

1543
来自专栏技术沉淀

Rails里实现Filter功能

873
来自专栏李蔚蓬的专栏

java.lang.NullPointerException: Attempt to invoke virtual method 'int android.content.Intent.getI...

这个报错比较骚,完全只是因为Intent没有写好而已,下面是错误的写法(最好不要在方法外赋值):

5182
来自专栏ml

HDUOJ----2952Counting Sheep

Counting Sheep Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/327...

3427
来自专栏SAP最佳业务实践

SAP S/4HANA最佳业务实践:Order-to-Cash订单到收款-5订单处理

•The tile Manage Sales Orders is part of the business catalog Sales –Sales Order...

39312

扫码关注云+社区

领取腾讯云代金券