Proficient.
Put your skills to the test.

Problem summary

Initially N glasses are empty. An update adds one unit of a specified drink to every glass in [L,R]. A query asks whether all glasses in [L,R] contain exactly the same amount of every drink.

Constraints

1 ≤ N,Q ≤ 200000; 1 ≤ X ≤ 100000; 1 ≤ L ≤ R ≤ N.

Worked example

An independently prepared example for this explanation.

4 7
2 1 3
1 1 3 5
1 3 4 6
2 1 3
2 1 2
1 2 2 5
2 1 2

1
0
1
0

Solution analysis

1. Compare neighboring glasses instead of storing every mixture. For each boundary i between glasses i−1 and i, maintain the exact per-drink difference mixture[i]−mixture[i−1]. An interval is uniform if and only if every internal boundary is zero.
2. Adding drink X to [L,R] changes only two boundary coordinates: add one to (L,X), subtract one from (R+1,X). Store nonzero coordinates in an ordered map keyed by boundary and drink. For each boundary, count how many drink coordinates are nonzero.
3. A Fenwick tree stores one for every nonzero boundary. Query [L,R] is true exactly when the sum over boundaries L+1 through R is zero. In the sample, adding drink 6 to glasses 3 and 4 creates a difference at boundary 3, so [1,3] fails while [1,2] remains uniform. This method compares exact counts and needs no hash-collision assumption.

Why it works

The discrete difference of a range addition is zero except at its two endpoints, so map updates preserve every neighboring mixture difference exactly. A difference vector is zero precisely when its nonzero-coordinate count is zero. Equality propagates along an interval if and only if all its internal neighboring differences are zero, exactly the Fenwick query condition.

Watch out. Ignore boundary 1 and boundary N+1 because queries use only actual neighboring pairs. Remove zero map entries. Query the internal boundaries L+1..R, so a singleton interval always succeeds.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<map>
#include<utility>
// Algorithm: Compare neighboring glasses instead of storing every mixture.
using namespace std;
struct Fenwick{
    vector<int>tree;
    explicit Fenwick(int n):tree(n+1,0){
    }
    void add(int index,int value){
        for(;index<static_cast<int>(tree.size());index+=index&-index){
            tree[index]+=value;
        }
    }
    int prefix(int index)const{
        int result=0;
        for(;index>0;index-=index&-index){
            result+=tree[index];
        }
        return result;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    map<pair<int,int>,int>difference;
    vector<int>nonzero(n+1,0);
    Fenwick active(n);
    auto change=[&](int boundary,int drink,int delta){
        if(boundary<=1||boundary>n){
            return;
        }
        pair<int,int>key={boundary,drink};
        auto it=difference.find(key);
        int oldValue=it==difference.end()?0:it->second;
        int newValue=oldValue+delta;
        bool wasActive=nonzero[boundary]>0;
        if(oldValue==0){
            ++nonzero[boundary];
        }
        if(newValue==0){
            --nonzero[boundary];
            difference.erase(key);
        }
        else{
            difference[key]=newValue;
        }
        bool isActive=nonzero[boundary]>0;
        if(wasActive!=isActive){
            active.add(boundary,isActive?1:-1);
        }
    };
    while(q--){
        int type,left,right;
        cin>>type>>left>>right;
        if(type==1){
            int drink;
            cin>>drink;
            change(left,drink,1);
            change(right+1,drink,-1);
        }
        else{
            cout<<(active.prefix(right)==active.prefix(left)?1:0)<<'\n';
        }
    }
}