Light on or off

Light on or off

时间: 2ms        内存:64M

描述:

There is N lights on the wall of Dreamone’s house from left to right.Initially,some lights on and some lights off, and we use ‘1’ represented the light on, use ‘0’ represented the light off. As we know, there is a cat in dremone’s house, and she is very naught. She always change the status continuously from Ath light to Bth one. (1<=A, B<=N).If the light is on, then the light will be off, If the light is off, then the light will be on.
Actually, she can do it K times like this. Then the cat puts forward another problem: How many lights on from Cth light to Dth (1<=C, D<=N) one? For example:
When N=4 K=2, and the initial status is assumed as:
1 0 1 1
‘1’ represented on,’0’ represented off.
From the initial status we can get: There is 3 lights on from 1st light to 4th, 2 lights on from 2nd to 4th and so on. Then we assume the first operation that we change the status from 2nd to 4th, and then the status will be:
1 1 0 0
Then there are 2 lights on from 1st light to 4th one, 1 light on from 2nd to 4th one and so on. Then the second operation is assumed as from the 1st to 2nd .Then the status will be 0 0 0 0. And there will be no lights on.
Can you get the main idea? Can you help the naught cat?

输入:

The first line of input will be a positive integer indicating how many test cases will be included (T) and T will be less than 10. Each of the next T cases will contain two parts:
The first part: two integer N, K (1<=N<=100000, 1<=K<=100000)
The second part: N numbers (which is ‘0’ or ‘1’) represented the initial status from left to right.
Then third part: K lines. Each line will be X C D (1<=C, D<=N) X is a letter which is either ‘Q’ or ‘C’. If X=’Q’, you will be output the numbers of lights on from Cth to Dth, and if X=’C’, you will be change the status of lights as the rules described above.

输出:

For each query,(when X=’Q’)you should output the numbers of lights on. What’s more, you must output a blank line after you have processed a test case.

示例输入:

2
4 3
1 0 1 1
Q 2 4
C 2 3
Q 1 4
4 1
1 0 1 1
Q 2 4

示例输出:

2
3

2

提示:

参考答案(内存最优[6348]):

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;

int num[100001];

struct node{
	int l;
	int r;
	int sum;
	int flag;
};
node tree[3*100001];
int s,n;

void build(int k,int l,int r){
	tree[k].l=l;
	tree[k].r=r;
	tree[k].flag=0;
	tree[k].sum=0;
	if(l==r){
		tree[k].sum=num[l];
		return ;
	}
	int mid=(l+r)/2;
	build(2*k,l,mid);
	build(2*k+1,mid+1,r);
	tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
}

void query(int k,int l,int r){
	if(tree[k].l==l&&tree[k].r==r){
		s+=tree[k].sum;
		return ;
	}
	if(tree[k].flag){
		tree[2*k].flag=1-tree[2*k].flag;
		tree[2*k].sum=(tree[2*k].r-tree[2*k].l+1)-tree[2*k].sum;

		tree[2*k+1].flag=1-tree[2*k+1].flag;
		tree[2*k+1].sum=(tree[2*k+1].r-tree[2*k+1].l+1)-tree[2*k+1].sum;
	}
	tree[k].flag=0;
	int mid=(tree[k].l+tree[k].r)/2;
	if(r<=mid)
		query(2*k,l,r);
	else if(l>mid)
		query(2*k+1,l,r);
	else{
		query(2*k,l,mid);
		query(2*k+1,mid+1,r);
	}
}
void change(int k,int l,int r){
	if(tree[k].l==l&&tree[k].r==r){
		tree[k].flag=1-tree[k].flag;
		tree[k].sum=(tree[k].r-tree[k].l+1)-tree[k].sum;
		return ;
	}
	if(tree[k].flag){
		tree[2*k].flag=1-tree[2*k].flag;
		tree[2*k].sum=(tree[2*k].r-tree[2*k].l+1)-tree[2*k].sum;

		tree[2*k+1].flag=1-tree[2*k+1].flag;
		tree[2*k+1].sum=(tree[2*k+1].r-tree[2*k+1].l+1)-tree[2*k+1].sum;
	}
	tree[k].flag=0;
	int mid=(tree[k].l+tree[k].r)/2;
	if(r<=mid)
		change(2*k,l,r);
	else if(l>mid)
		change(2*k+1,l,r);
	else{
		change(2*k,l,mid);
		change(2*k+1,mid+1,r);
	}
	tree[k].sum=tree[2*k].sum+tree[2*k+1].sum;
}
int main(){
	char ch[3];
	int cc,i,a,b;
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&cc);
		for(i=1;i<=n;i++)
			scanf("%d",&num[i]);
		build(1,1,n);
		while(cc--){
			scanf("%s%d%d",&ch,&a,&b);
			if(a>b){int tmp=a;a=b;b=tmp;}
			if(ch[0]=='Q'){
				s=0;
				query(1,a,b);
				printf("%d\n",s);
			}
			else if(ch[0]=='C'){
				change(1,a,b);
			}
		}
		printf("\n");
	}	
	return 0;
}

参考答案(时间最优[121]):

#include <cstdlib>  
#include <stdio.h>  
#include <string.h>  
#define N 100500  
/* 
 *  
 */  
int v[N];  
void swap(int &a,int &b)  
{  
    a^=b;  
    b^=a;  
    a^=b;  
}  
struct tree  
{  
    int l,r,sum,state;  
    int mid()  
    {  
        return (l+r)>>1;  
    }  
}T[N*4];  
void build(int l,int r,int root)  
{  
    T[root].l=l,T[root].r=r;  
    T[root].state=0;  
    if(l==r)  
    {  
        T[root].sum=v[l];  
        return ;  
    }  
    int mid=T[root].mid();  
    build(l,mid,root<<1);  
    build(mid+1,r,root<<1|1);  
    T[root].sum=T[root<<1].sum+T[root<<1|1].sum;  
}  
void modify(int l,int r,int root)  
{  
    if(T[root].l==l&&T[root].r==r)  
    {  
        T[root].state=1-T[root].state;  
        T[root].sum=T[root].r-T[root].l+1-T[root].sum;  
        return ;  
    }  
    if(T[root].state)  
    {  
        T[root<<1].state=1-T[root<<1].state;  
        T[root<<1|1].state=1-T[root<<1|1].state;  
        T[root<<1].sum=T[root<<1].r-T[root<<1].l+1-T[root<<1].sum;  
        T[root<<1|1].sum=T[root<<1|1].r-T[root<<1|1].l+1-T[root<<1|1].sum;  
        T[root].state=0;  
    }  
    int mid=T[root].mid();  
    if(r<=mid)  
        modify(l,r,root<<1);  
    else if(l>=mid+1)  
        modify(l,r,root<<1|1);  
    else  
    {  
        modify(l,mid,root<<1);  
        modify(mid+1,r,root<<1|1);  
    }  
    T[root].sum=T[root<<1].sum+T[root<<1|1].sum;  
}  
void query(int l,int r,int root,int &ans)  
{  
    if(T[root].l==l&&T[root].r==r)  
    {  
        ans+=T[root].sum;  
        return ;  
    }  
    if(T[root].state)  
    {  
        T[root<<1].state=1-T[root<<1].state;  
        T[root<<1|1].state=1-T[root<<1|1].state;  
        T[root<<1].sum=T[root<<1].r-T[root<<1].l+1-T[root<<1].sum;  
        T[root<<1|1].sum=T[root<<1|1].r-T[root<<1|1].l+1-T[root<<1|1].sum;  
        T[root].state=0;  
    }  
    int mid=T[root].mid();  
    if(r<=mid)  
        query(l,r,root<<1,ans);  
    else if(l>=mid+1)  
        query(l,r,root<<1|1,ans);  
    else  
    {  
        query(l,mid,root<<1,ans);  
        query(mid+1,r,root<<1|1,ans);  
    }  
}  
int main(int argc, char** argv)   
{  
    int t,n,q,i;  
    scanf("%d",&t);  
    while(t--)  
    {  
        scanf("%d%d",&n,&q);          
        for(i=1;i<=n;i++)  
            scanf("%d",&v[i]);  
        build(1,n,1);  
        while(q--)  
        {  
        char str[2];  
        int a,b,ans=0;  
        scanf("%s%d%d",str,&a,&b);  
        if(a>b)  
            swap(a,b);  
        if(str[0]=='Q')  
        {  
            query(a,b,1,ans);  
            printf("%d\n",ans);  
        }  
        else  
            modify(a,b,1);  
        }  
        puts("");  
    }  
    return 0;  
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注