SPOJ

FREQUENT                                                         segment tree #include <iostream> #include <algorithm> #include <stdio.h> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) #define pii pair<int, int> #define mp make_pair #define f first // value #define s second //frequency #define FOR(a, b) for(int i = a; i < b; i++) using namespace std; const int N = 100001; struct node {     pii m;     pii l;     pii r; }; int n, q; int arr[N]; node seg[4 * N]; node combine(node &a, node &b) {     node res;     if(a.l.f == b.r.f) //if all the elements are same     {         res.l.f = res.r.f = res.m.f = a.l.f;         res.l.s = res.r.s = res.m.s = a.l.s + b.r.s;     }     else     {         res.l = a.l;         res.r = b.r;         if(a.l.f == b.l.f) //if first element of left is same as first element of right         {    

                                              D-Query                                            segment tree + offline method #include <iostream> #include <algorithm> #include <stdio.h> #include <map> #define sf(i) scanf("%d", &i) #define pf(i) printf("%d\n", i) using namespace std; const int N = 30001; const int Q = 200001; struct node {     int l, r;     int pos,     int val; }; int n, q; node arr[N + Q]; int result[Q]; int seg[4 * N]; map<int, int> last_pos; node makenode(int l, int r, int pos, int val) {     node temp;     temp.l = l;     temp.r = r;     temp.pos = pos;     temp.val = val;     return temp; } void update(int l, int r, int index, int pos, int val) {     if(l == r)     {         seg[index] = val;     }     else     {         int mid = (r + l) / 2;         if(pos <= mid)         {             update(l, mid, 2 * i