线段树吧 关注:19贴子:116
  • 4回复贴,共1

【题随线动】简单题

只看楼主收藏回复

一楼献度娘


1楼2011-02-13 17:38回复
    有一个n个元素的数组,每个元素初始均为0。有m条指令,要么让其中一段连续序列数字反转——0变1,1变0(操作1),要么询问某个元素的值(操作2)。例如当n=20时,10条指令如下: Input
      第一行包含两个整数n,m,表示数组的长度和指令的条数,以下m行,每行的第一个数t表示操作的种类。若t=1,则接下来有两个数L, R (L<=R),表示区间[L, R]的每个数均反转;若t=2,则接下来只有一个数I,表示询问的下标。
    Output
      每个操作2输出一行(非0即1),表示每次操作2的回答
    Sample Input
    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
    Sample Output
    1 0 0 0 1 1
    


    3楼2011-02-13 17:39
    回复
      #include<iostream>#include<cmath>#include<cstdio>using namespace std;int c[10001],n,t,ttt,m;int lowbit(int x){ return x&(x^(x-1));}void pluse(int p){ while(p>0) { c[p]++; p-=lowbit(p); }}int pin(int x){ int tt; tt=0; while(x<=n) { tt+=c[x]; x+=lowbit(x); } return tt;}int main(){ freopen("easy.in","r",stdin); freopen("easy.out","w",stdout); int i,x,y; scanf("%d%d",&n,&m); for (i=1;i<=m;i++) {scanf("%d",t); if (t==1) {scanf("%d%d",&x,&y); pluse(y); pluse(x-1);} else {scanf("%d",&x); cout<<pin(x)%2<<endl;} } //system("pause"); fclose(stdin);fclose(stdout);}


      4楼2012-03-23 22:49
      回复
        确实很简单、
        可以直接用zkw加标记永久化做、
        好吧、线段树貌似只有区间修改区间查询zkw不好写、


        5楼2012-03-29 14:27
        回复
          #include <cstdio>
          #include <iostream>
          #define lson l , m , rt << 1
          #define rson m+1 , r ,rt << 1 | 1 #define maxn 11111
          using namespace std;
          int sum[maxn<<2];
          int Sum;
          void build(int l,int r,int rt){
          if (l == r) return ;
          int m = (l + r) >> 1;
          build (lson);
          build (rson);
          }
          void update(int L,int R,int l,int r,int rt){
          if (L <= l && r <= R){
          sum[rt]++;
          return ;
          }
          int m = (l + r) >> 1;
          if (L <= m) update (L , R , lson);
          if (R > m) update (L , R , rson);
          }
          void query(int p,int l,int r,int rt){
          if (p <= r && p >= l){
          Sum += sum[rt];
          }
          if (l == r) return ;
          int m = (l + r) >> 1;
          if (p <= m) query(p , lson);
          else query(p , rson);
          }
          int main(){
          freopen ("easy.in","r",stdin);
          freopen ("easy.out","w",stdout);
          int n,m;
          scanf("%d%d",&n,&m);
          build(1 , n , 1);
          for (int cas=1 ; cas<=m ; ++cas){
          int a,b,c;
          scanf("%d",&a);
          if (a == 1){
          scanf("%d%d",&b,&c);
          update (b , c , 1 , n , 1);
          }
          else {
          scanf("%d",&b);
          Sum=0;
          query(b , 1 , n , 1);
          printf("%d\n", Sum % 2);
          }
          }
          return 0;
          }
          


          IP属地:上海6楼2012-03-31 15:42
          回复