NYOJ----1124數量

數量

描述

HJS大牛想去街上吃飯，街道旁邊拴著很多狗，他想我堂堂......（省略n個字）豈會被狗咬，所以他很牛的從狗的面前經過，不管是否被上一條狗咬過，下次還會從狗的面前過（J I A N）

現在問題來了，我們給狗編號從1...n，有多次詢問，每次詢問M,N這一段有多少狗咬過他有多少狗沒有咬過他

輸入

輸入有多組數據，每組數據有N,M代表N個狗，M次詢問(n<=1000000)
接下來一行有n個數正數代表被狗咬，負數代表不咬，0代表不確定看心情，所以我們只計算確定的就可以了
接下來M行每行兩個數a，b代表a到b這一段

輸出

每次查詢輸出一行，每行兩個數中間有一個空格，分別代表咬人的狗的數量，沒咬人的數量

樣例輸入

5 6
-1 -2 3 4 5
1 2
1 3
1 4
2 4
3 5
1 5

樣例輸出

0 2
1 2
2 2
2 1
3 0
3 2

//主要是要剔除0，即不確定的數量
#include <stdio.h>
int ydog[1000001],dog[1000001],flag[1000001],flag1[1000001];//定義全局變數區而不可定義為棧區(棧溢出),s[0] = 0
int main()
{
    int N,M,i,a,b,s;
    while(scanf("%d%d",&N,&M) != EOF)  
    {
        for(i=1;i<=N;i++)
        {
            scanf("%d",&ydog[i]);
            if(ydog[i] > 0)
            {
                dog[i] = dog[i-1] + 1;//dog[0] = 0
                flag[i] = 1;//咬人 
                flag1[i] = flag1[i-1];//要剔除的0的個數和前一個相同 
            }
            else{
                dog[i] = dog[i-1];//dog[0] = 0
                flag[i] = 0;//不確定和確定不咬人的 
                if(ydog[i] == 0)
                    flag1[i] = flag1[i-1] + 1;//要剔除掉0(不確定)
                else{
                    flag1[i] = flag1[i-1];
                }
            }
        }
        for(i=1;i<=M;i++)
        {
            scanf("%d%d",&a,&b);//編號 
            printf("%d %d\n",dog[b]-dog[a]+flag[a],(b-a+1-(flag1[b]-flag1[a]+(!ydog[a])))-(dog[b]-dog[a]+flag[a]));
        }
    }
    return 0;
}

 

//----JZT_wuyang
#include <stdio.h>
int main()
{
    int n, m, x, y, z, i, a[100005] = {0}, b[100005] = {0};
    while (~scanf("%d%d", &n, &m))
    {
        for (i = 1, y = z = 0; i <= n; i++)
        {
            scanf("%d", &x);
            if (x > 0)
                y ++;
            else if (x < 0)
                z ++;
            a[i] = y;
            b[i] = z;
        }
        while (m--)
        {
            scanf("%d%d", &x, &y);
            printf("%d %d\n", a[y]-a[x-1], b[y]-b[x-1]);
        }
    }
    return 0;
}