ציילן און טאַגאַל פֿראגן אויף אַ ביינערי עריי


שוועריקייט לעוועל שווער
אָפט געבעטן אין אַמאַזאָן facebook גוגל ובער
מענגע אָפּשניט-טרי

An מענגע פון גרייס n איז געגעבן ווי אַ אַרייַנשרייַב ווערט. די פּראָבלעם "גראף און טאַגאַל פֿראגן אויף אַ ביינערי עריי" פרעגט צו דורכפירן עטלעכע פון ​​די פֿראגן וואָס זענען אונטן. פֿראגן קענען זיין אַנדערש אין אַ טראַפ - שטייגער.

די פֿראגן זענען ⇒

טאַגאַל אָנפֿרעג ⇒ טאַגאַל (סטאַרטינג, סאָף), דעם טאַגאַל אָנפֿרעג מיטל, טוישן 0 ס אין 1 אָדער 1 ס אין 0 ס ין דער געגעבן קייט.

גראף אָנפֿרעג ⇒ ציילן (סטאַרטינג, סאָף), דעם ציילן אָנפֿרעג מיטל צו ציילן אַלע די נומער פון אָנעס אין די געגעבן קייט.

בייַשפּיל

n = 5
toggle(0, 1)
toggle(2, 3)
count(1, 2)
toggle(1, 4)
count(0, 2)
Count of all the ones within the range 1 and 2 is 2.
The count of all the ones within the range 0 and 2 is 1.

דערקלערונג: דער ציילן פון איינער איז געדרוקט אויף יעדער ציילן אָנפֿרעג.

ציילן און טאַגאַל פֿראגן אויף אַ ביינערי עריי

אַלגאָריטהם

  1. קוק אויב די באָאָלעאַן באָאָלטרעע איז אמת אָדער פאַלש. אויב עס איז אמת, צייכן דעם נאָדע ווי פאַלש. דערהייַנטיקן די ווערט אין סעגמענטטרעע ווי סאָף - סטאַרטינג + 1 סעגמענטטרעע [נאָדע].
  2. קאָנטראָלירן אויב עס איז נישט אַ בלאַט נאָדע, באַשטעטיקן אָדער יבערקערן די ווערט פון באָאָלטרעע פון קינדער.
  3. אויב די וואַלועס זענען אויס פון קייט, דאַן צוריקקומען.
  4. קוק אויב די סעגמענטטרעע אויב עס איז אמת, דערהייַנטיקן די קראַנט קראַנט עלעמענט פון SegmentTree ווי די חילוק און טשעק ווידער אויב עס איז נישט אַ בלאַט נאָדע און טאָן די זעלבע פּראָצעדור ווי אין שריט 2.
  5. קאָנטראָלירן אויב די SegmentTree איז נישט אין די קייט און די וואַלועס זענען לאַפּינג אויף יעדער זייַט פון די SegmentTree און טאָן רעקורסיווע רופן.
  6. דערהייַנטיקן די ווערט פון די קראַנט נאָדע פון ​​די SegmentTree נאָדע ווי זייער קינדער רעזולטאַט.

פֿאַר ציילן אָנפֿרעג

  1. קאָנטראָלירן אויב די קראַנט נאָדע איז אויס פון די קייט, דאַן צוריקקומען 0.
  2. דערנאָך זען אויב די קראַנט נאָדע פון ​​באָאָלטרעעס איז אמת, אויב אמת, צייכן די קראַנט נאָדע פון ​​באָאָלטרעעס צו פאַלש און דערהייַנטיקן די קראַנט נאָדע ווערט פון סעגמענטטרע ווי די חילוק.
  3. קאָנטראָלירן צי עס איז נישט אַ בלאַט נאָדע און יבערקערן די וואַלועס פון די קינדער.
  4. קאָנטראָלירן אויב די SegmentTree ליגט אין די געגעבן קייט, און צוריק די SegmentTree [נאָדע].
  5. אויב נישט די, רעקורסיוועלי רופן די פֿונקציע אַזוי אַז עס נישט אָוווערלאַפּס.

דערקלערונג

מיר האָבן געגעבן אַ מענגע פון ​​N אַזאַ אַז אַלע זייַן וואַלועס זענען ינישיייטיד צו 0. מיר וועלן דורכפירן צוויי פֿראגן וואָס זענען טאַגאַל אָנפֿרעג וואָס איז צו יבערקערן אַלע די 0 ס אין די 1 ס און אַלע די 1 ס אין די 0 ס ין די געגעבן קייט. . דער ציילן אָנפֿרעג איז צו ציילן אַלע די זעראָעס פאָרשטעלן אין די געגעבן קייט. מיר וועלן נוצן SegmentTree וואָס איז יניטיאַליזעד ווי 0. מיר קאַנווערט עס אין 1 ין די קייט.

ווען די גערופֿן דעם טאַגאַל פונקציע, מיר וועלן קוקן פֿאַר די באָאָלעאַן מענגע מיר באשאפן ווי באָאָלטרעע וואָס איז געווען ינישיייטיד ווי פאַלש, מיר וועלן קאָנטראָלירן אויב די באָולטרעע 'קראַנט נאָדע ווערט איז אמת אָדער פאַלש, אויב עס איז פאַלש, ניט געשען ביז איצט. אַזוי מיר דאַרפֿן צו טאָן דאָס, און אויב עס איז אמת, ערשטער, מיר צייכן עס ווי פאַלש, אַזוי מיר קענען נוצן עס שפּעטער און דערהייַנטיקן די ווערט פון SegmentTree אין די קראַנט נאָדע ווי די סומע פון ​​די חילוק פון ענדיקן און סטאַרטינג און די חילוק פון 1 און די קראַנט נאָדע ווערט פון SegmentTree. מיר וועלן קאָנטראָלירן צי עס איז נישט אַ בלאַט נאָדע, ווייַל אויב דאָס איז, מיר וועלן נישט מאַכן אַפּעריישאַנז נאָך דעם. אויב נישט, מיר וועלן דערהייַנטיקן די וואַלועס פון קינדער נאָדע ווי די באָאָלעאַן וואַלועס.

קאָנטראָלירן צי די קראַנט אָפּשניט פון SegmentTree איז ין אַ געגעבן קייט אָדער נישט. אויב ניט, טאָן רעקורסיווע רופן פֿאַר אַזאַ אַז די נאָדעס אָפּשניט קומט אין די געגעבן קייט.

דער זעלביקער זאַך איז צו טאָן מיט די ציילן פונקציע אָבער מיט אַ ביסל אַנדערש צוגאַנג. מיר וועלן קאָנטראָלירן אויב די קראַנט נאָדע זאָל ניט זיין אויס פון קייט אויב עס נאָר קערט די ווערט 0.

קאָנטראָלירן צי די קראַנט נאָדע זאָל נישט זיין אנגעצייכנט מיט די קראַנט נאָדע פון ​​SegmentTree. אויב אמת, דערהייַנטיקן די קראַנט נאָדע ווי פאַלש, און דערהייַנטיקן די קראַנט נאָדע ס וואַלועס פון SegmentTree ווי די סומע פון ​​די חילוק פון ענדיקן און סטאַרטינג און די חילוק פון 1 און די קראַנט נאָמע פון ​​SegementTree מיר האָבן דורכגעקאָכט אין די טאַגלינג פונקציאָנירן. נישט אַ בלאַט, מאַך פאָרויס מיט די דערהייַנטיקן פון די קינדער נאָודז. ביז איצט, מיר האָבן דורכגעקאָכט אַלע די פּרירעקוואַזאַט מעטהאָדס צו צוריקקריגן דעם ענטפער. מיר וועלן קאָנטראָלירן אויב די קראַנט אָפּשניט פון נאָדעס איז ין דער געגעבן קייט און צוריקקומען די קראַנט ווערט פון די SegementTree נאָדע. אַנדערש רעקורסיוועלי רופט די פֿונקציע צו מאַכן עס אין די קייט.

ימפּלעמענטאַטיאָן

C ++ קאָד צו ציילן און טאַגאַל פֿראגן אויף אַ ביינערי עריי

#include<iostream>
using namespace std;

const int MAX = 100000;

int segmentTree[MAX] = {0};

bool boolTree[MAX] = {false};

void toggle(int node, int starting, int ending, int rangeStart, int rangeEnding)
{
    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending - starting + 1 - segmentTree[node];

        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
    }
    if (starting>ending || rangeStart > ending || rangeEnding < starting)
        return ;
    if (rangeStart<=starting && ending<=rangeEnding)
    {
        segmentTree[node] = ending-starting+1 - segmentTree[node];
        if (starting < ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[1+(node<<1)] = !boolTree[1+(node<<1)];
        }
        return;
    }
    int mid = (starting+ending)/2;
    toggle((node<<1), starting, mid, rangeStart, rangeEnding);
    toggle((node<<1)+1, mid+1,ending, rangeStart, rangeEnding);
    if (starting < ending)
        segmentTree[node] = segmentTree[node<<1] + segmentTree[(node<<1)+1];
}

int count(int node, int starting, int ending, int qs, int qe)
{
    if (starting>ending || qs > ending || qe < starting)
        return 0;

    if (boolTree[node])
    {
        boolTree[node] = false;
        segmentTree[node] = ending-starting+1-segmentTree[node];

        if (starting<ending)
        {
            boolTree[node<<1] = !boolTree[node<<1];
            boolTree[(node<<1)+1] = !boolTree[(node<<1)+1];
        }
    }
    if (qs<=starting && ending<=qe)
        return segmentTree[node];

    int mid = (starting+ending)/2;
    return count((node<<1), starting, mid, qs, qe) +
           count((node<<1)+1, mid+1, ending, qs, qe);
}

int main()
{
    int n = 5;
    toggle(1, 0, n-1, 0, 1);
    toggle(1, 0, n-1, 2, 3);
    cout << count(1, 0, n-1, 1, 2) << endl;
    toggle(1, 0, n-1, 1, 4);
    cout << count(1, 0, n-1, 0, 2) << endl;

    return 0;
}
2
1

דזשאַוואַ קאָד צו ציילן און טאַגאַל פֿראגן אויף אַ ביינערי עריי

class toggleAndCount
{
    static final int MAX = 100000;

    static int segmentTree[] = new int[MAX];

    static boolean boolTree[] = new boolean[MAX];

    static void toggle(int node, int starting,int ending, int rangeStart, int rangeEnding)
    {
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
        }
        if (starting > ending || rangeStart > ending || rangeEnding < starting)
        {
            return;
        }
        if (rangeStart <= starting && ending <= rangeEnding)
        {
            segmentTree[node] = ending - starting + 1 - segmentTree[node];
            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[1 + (node << 1)] = !boolTree[1 + (node << 1)];
            }
            return;
        }

        int mid = (starting + ending) / 2;
        toggle((node << 1), starting, mid, rangeStart, rangeEnding);
        toggle((node << 1) + 1, mid + 1, ending, rangeStart, rangeEnding);
        if (starting < ending)
        {
            segmentTree[node] = segmentTree[node << 1] +segmentTree[(node << 1) + 1];
        }
    }
    static int count(int node, int starting,int ending, int qs, int qe)
    {
        if (starting > ending || qs > ending || qe < starting)
        {
            return 0;
        }
        if (boolTree[node])
        {
            boolTree[node] = false;
            segmentTree[node] = ending - starting + 1 - segmentTree[node];

            if (starting < ending)
            {
                boolTree[node << 1] = !boolTree[node << 1];
                boolTree[(node << 1) + 1] = !boolTree[(node << 1) + 1];
            }
        }
        if (qs <= starting && ending <= qe)
        {
            return segmentTree[node];
        }
        int mid = (starting + ending) / 2;
        return count((node << 1), starting, mid, qs, qe) + count((node << 1) + 1, mid + 1, ending, qs, qe);
    }
    public static void main(String args[])
    {
        int n = 5;

        toggle(1, 0, n-1, 0, 1);
        toggle(1, 0, n-1, 2, 3);
        System.out.println( count(1, 0, n-1, 1, 2));
        toggle(1, 0, n-1, 1, 4);
        System.out.println(count(1, 0, n-1, 0, 2));
    }
}

2
1

קאַמפּלעקסיטי אַנאַליסיס פֿאַר גראף און טאַגאַל פֿראגן אויף אַ ביינערי עריי

צייט קאַמפּלעקסיטי

אָ (ק * קלאָץ n) ווו "Q" איז די נומער פון פֿראגן און “N” איז די גרייס פון דעם מענגע.

ספעיס קאַמפּלעקסיטי

אָ (N) ווו “N” איז די גרייס פון דעם מענגע.

דערמאָנען