c++ problem

[manacher1]

I have been given a problem by my teacher which I can not solve. I have a sequence of numbers given and some operations: change the value at a given position or : you are given an interval [a,b] and you have to find what term appears only once in that interval knowing that there is only one term that apper once and all the other terms in the interval occur an even number of times. Can someone please give me some hints (or just what data structure should I use) about how should a think at this problem?

f >> N >> M;

for ( int i = 1; i <= N; i++ )
    f >> v[i];

for ( int c, a, b ; M; M-- ){

    f >> c >> a >> b;

    if ( c == 0 ){

        int s = 0;

        for ( int i = a; i <= b; ++i )
            s ^= v[i];

        g << s << "\n";
    }
    else
        v[a] = b;
}

I wrote a "brute-force" but my solution is not the good one. In my brute-force I am calculating the xor sum of the interval values but this solution will not work if I have many intervals. I am thinking that interval tree will be good for this problem but I am not sure and also I cand figure out how to implement IT in this situation

[keskiverto]

If the interval were sorted, then each a[2n] would equal a[2n+1], until you reach the unique.

[manacher1]

but they are not

[keskiverto]

Is std::sort( v[a], v[b+1] ); allowed?

[manacher1]

It is but it isn't efficient...I am thinking about using interval trees or something like that..

[keskiverto]

Now you made me read about intervals ... lets see if I understand the task correctly:

1. You have a list of values, say: std::vector<int> v;
2. You are given two values: a and b, where a <= b.
3. A value v[i] in list is in the interval, if ( a <= v[i] && v[i] <= b )

If I'm correct so far, then you have to look at each v[i] in v. Given the other info, there is only one value that is in the interval exactly once. std::set

[manacher1]

I am not sure you understand right: v[i] is in the interval if ( a <= i && i <= b )

[keskiverto]

In that case term interval should be changed into term range.

Simpler, really. Iterate only range v+a, v+b+1. Each value either is in set of found values, or is not. If not, then add. If yes, then remove. Who are in the set after that?