23 noemvri
  2D Segment Tree


28 septemvri

Josif's idea: line sweep on range tree on all xes for every y coordinate
  Make segment tree of segment trees. where leaf is a single y coordinate segment trees over x
  every internal node is the sum of the two segment trees in the children => O(log(n)^2) per query

  root represents all x, all y: two children: A, B. Root has one more segmen tree in it where you can do any x query with -inf< y <inf range
	A represents all x, <Y/2, B represents all x, >Y/2
  A also has a tree that queries all x, -inf < y< Y/2




//In July
Hint za Sport: greedy za 30%

  int main()
{
    string a, b;
    cin >> a >> b;
    int n = a.size();
    int numA = 0, numB = 0;
    bool are_paired = true;
    for(int i=0;i<n;i++)
    {
        if(a[i]=='P')
        {
            numA++;
        }
        if(b[i]=='P')
        {
            numB++;
        }
        if(a[i]!=b[i])
        {
            are_paired = false;
        }
    }
    if(numA+numB == 2*n)
    {
        cout << -1;
        return 0;
    }
    else if(are_paired)
    {
        cout << numA <<endl;
        return 0;
    }
    else
    {
        cout << min(numA, numB)+1 <<endl;
    }
    return 0;
}

16 july


  http://codeforces.com/problemset/problem/86/D
query
  https://www.hackerearth.com/practice/notes/mos-algorithm/
  a1, b1
	void add(int idx)
    cnt[idx] ++;

    sort(a1.L / blockSize < b1.L / blockSize)
    a1.R < b1.R
    i++
    int mo_Left =0, mo_Right = -1;
    for(int i =0; i < q; i ++){
    int left = Q[i].L;
    int right = Q[i].R;
      while(moLeft < left)
        moLeft ++;
    	  add(moLeft);
      while(moLeft > left)

      while(moRight > right)

      while(moRight < right)





#include <fstream>
#include <iomanip>
#include <iostream>

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>

#define P push
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define DEC 0.00000001
#define MAX 2139062143
#define MAX_63  1061109567
#define MAXll 9187201950435737471
#define bp(a) __builtin_popcount(a)
#define rand(a, b) ((rand()%(b-a+1))+a)
#define MEM(a, b) memset(a, b, sizeof(a))
#define sort_v(a) sort(a.begin(), a.end())
#define rev_v(a)  reverse(a.begin(), a.end())

//#define fin cin
//#define fout cout
using namespace std;
//ifstream fin(".in");
//ofstream fout(".out");

#define set_bit(A,bit) (A|=(1<< (bit)))
#define clear_bit(A,bit) ((A&=~(1 << (bit))))
#define test_bit(A,bit) ((A&(1<<(bit)))!=0)

string s;
string t;

int letters[27];
vector<int> q;
int main()
{
    cin >> s;
    cin >> t;
    MEM(letters, 0);
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]!='?')
        letters[s[i]-'0']++;
        else
        {
            q.pb(i);
        }
    }
    int possible = true;
    vector<char> kraj;
    while(possible)
    {
        for(int i = 0;i<t.size();i++)
        {
            if(letters[t[i]-'0']>0)
            {
                letters[t[i]-'0']--;
            }
            else
            {
                if(q.size()>kraj.size())
                {
                    kraj.pb(t[i]);
                }
                else
                {
                    possible = false;
                    break;
                }
            }
        }
    }
    int kraj_at = 0;
    for(int i = 0;i<s.size();i++)
    {
        if(s[i]!='?')
        cout << s[i];
        else
        {
            cout << kraj[kraj_at];
            kraj_at++;
        }
    }
    cout << endl;
    return 0;
}


s: aza?
t: az

a[]: 2
z[]: 1
?[]: 1

construct: az,

a[]: 1
z[]: 0
?[]: 1

construct: az:


a[]: 0
z[]: 0
?[]: 0

az


14 juni
 #include <iostream>
using namespace std;
typedef long long ll;
int n, q;
ll arr[100001];
const ll inf = (1LL << 30ll);
struct elem{
    ll prefSum, suffSum, sum, mxx;
    elem(){}
    elem(ll _p, ll _suff, ll _sum, ll _mxx){
        prefSum = _p;
        suffSum = _suff;
        sum = _sum;
        mxx = _mxx;
    }
};
elem mymerge(elem a, elem b){
    elem tmp;
    tmp.sum = a.sum + b.sum;
    tmp.prefSum = max(a.prefSum, a.sum + b.prefSum);
    tmp.suffSum = max(b.suffSum, b.sum + a.suffSum);
    tmp.mxx = max(tmp.sum, max(tmp.prefSum, max(tmp.suffSum, max(a.mxx, max(b.mxx, a.suffSum + b.prefSum)))));
    return tmp;
}
ll rr;
class node{
public:
    elem val;
    int leftBound, rightBound;
    node *left, *right;
    node(int levo, int desno){
        leftBound = levo;
        rightBound = desno;
        if(levo == desno){
            val = elem(arr[levo], arr[levo], arr[levo], arr[levo]);
        }
        else{
            int mid = (levo + desno) / 2;
            left = new node(levo, mid);
            right = new node(mid + 1, desno);
            val = mymerge(left -> val, right -> val);
        }
    }
    void update(int &_node, elem &newVal){
        if(leftBound == rightBound){
            val = newVal;
            return;
        }
        if(_node >= right -> leftBound){
            right -> update(_node, newVal);
        }
        else{
            left -> update(_node, newVal);
        }
        val = mymerge(left -> val, right -> val);
    }
    elem query(int &i, int &j){
        if(i <= leftBound && rightBound <= j){
            rr = max(rr, val.mxx);
            return val;
        }
        else if(rightBound < i || j < leftBound){
            return elem(-inf, -inf, -inf, -inf);
        }
        return mymerge(left -> query(i, j), right -> query(i, j));
    }
};
int main(int argc, const char * argv[]) {
    //    ifstream cin("in.txt");
    //    ofstream cout("out.txt");
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> arr[i];
    }
    cin >> q;
    int a, b;
    int t;
    node segmentTree(0, n - 1);
    for(int i = 0; i < q; i ++){
        cin >> t >> a >> b;
        if(t == 0){
            a --;
            elem tmp((ll)b, (ll)b, (ll)b, (ll)b);
            segmentTree.update(a, tmp);
        }
        else{
            a --;
            b --;
            rr = -inf;
            ll t = segmentTree.query(a, b).mxx;
            cout << max(rr, t)  << endl;
        }
    }
    return 0;
}

datop
30 april
//adadasdasd
  #include <bits/stdc++.h>

using namespace std;
#define EPS 1e-7
int n, m;
vector<double> pc, power;
double mid;
bool areEqual(double a, double b){
    return (a - b) < EPS || (a < b);
}
short int dp[101][1 << 16];
bool rek(int at, int pos, int visited, double passedTime){
    if(!areEqual((passedTime) / power[at], mid))return false;

    if(pos == m){
        return true;
    }

    if(dp[pos][visited] != -1){
        return dp[pos][visited;
      //neam memoizacija
    }
    bool ret = true;
    if(areEqual((passedTime + pc[pos]) / power[at], mid)){ //Tuka is? tuka vikam ako mozam da prodolzam so covekot na pozicija at
        return  dp[pos][visited] = rek(at, pos + 1, visited, passedTime + pc[pos]);// da da ok, sfakjam. Epa mislam deka radi ova pagja. sekoj pat vikash rekurzija +1, a mozesh da skoknesh odma +max_kolku_shto_mozesh
    }
    for(int i = 0; i < n; i ++){
        if(!(visited & (1 << i))){
       int     newMask = visited;
            newMask |= (1 << i);
            if(areEqual((pc[pos] / power[i]), mid))
                if(rek(i, pos + 1, newMask, pc[pos])){
                    return dp[pos][visited] = true;
                }
        }
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);

    cin >> m >> n;
    double tmp;
    for(int i = 0; i < m; i ++){
        cin >> tmp;
        pc.push_back(tmp);
    }
    for(int i = 0; i < n; i ++){
        cin >> tmp;
        power.push_back(tmp);
    }
    double levo = 0.0;
    double desno = 200000.0;
    while(fabs(levo - desno) > EPS){
        mid = levo + (desno - levo) / 2;
        //if(mid < 0.0)break;
        bool da = false;
 	memset(dp, -1, sizeof dp);
        for(int i =0; i < n;i ++){
             //               memset(dp, -1, sizeof  dp);

            if(rek(i, 1, (1 << i), pc[0])){
                da = true;
                break;
            }
        }
        if(da){
         //      printf("%.6f\n", mid);
            desno=  mid  ;

        }
        else{
            levo = mid ;
        }

    }
    printf("%.6f", levo);
    return 0;
}

  double time;

  bool rek(int person, int pos, int visited, double passedRooms_per_person)

  	if(time <= passedRooms_per_person / power[at]) <<<
    	rek(person, pos + 1, visited, passedRooms + pc[pos])
    else{
    return false;
    for(int i =0 ; i < n;  i++){
    if(!(visited & (1 << i))
       if(pc[pos] / power[i] >= time)
       rek(i, pos + 1, visited | (1 << i), pc[pos])



	bool rek(room_at, vis)
     if(room_at == end) return true;
     if(vis is all 1) return false;

     for(int i=0;i<n;i++)
       {
       		if(!(vis&(1<<i))
             {
               int tmp = rek(get_max_to_the_right[room_at][i], vis|(1<<i))
               if(tmp == 1)
               {
                 return 1;
               }
             }
       }
     return 0;




16 april


  Asistent: http://mendo.mk/Task.do?id=379


  part: bop

  palindrom: boppob
  verglanje: boppobboppob

              i
 $_b_o_p_p_o_b_b_o_p_p_o_b_@
  ^     ^     ^               <<obelezuvanje
  L           C           R
    0303031303032
        3     5
  quarter = (R-L+3)/4 -> proveri tocno kako treba da e
  if(niz[quarter]*2 - 1 == niz[C]) = remember as possible solution


12 april
  Tifani od drzaven 2017
  http://mendo.mk/Task.do?id=714

dp[100001][4][4][4][4]
  dp[100001][2^3][2^3]
  s[at]



  dp[at][l_1][l_2][r_1][r_2] = max(rek(at + 1, l_2, curr, r_1, r_2) + x, rek(at+1, l_1, l_2, r_2, curr)+cost)

  dp[n][][][][] = dp[n-1][][][][] or
  dp[n][]][][] = dp[n+1][][][][] =>

  0 znaci deka at%2 = 1
  1 znaci deke at%2 = 0
  init:
  (dp[0][0][0][0][0] = 0) dali ni treba? < ne ni treba za dp-to za tiffany[1] deka e vekje vkluceno vo dp-to za tiffany[0]
  a = next = tiffany[0]
  dp[1][0][a][0][0] = dp[0][0][0][0][0] + reward : stavi go a levo na prazno
	dp[1][0][0][0][a] = dp[0][0][0][0][0] + reward : stavi go a desno na prazno
  b = next = tiffany[1];
  dp[0][0][a][0][b] = dp[1][0][a][0][0] + reward : prvo a bilo levo, sme go postavile b desno
  dp[0][a][b][0][0] = dp[1][0][a][0][0] + reward : prvo a bilo levo, sme go postavile b levo
  dp[0][0][b][0][a] = dp[1][0][0][0][a] + reward : a bilo desno, stavi go b desno
  dp[0][0][0][a][b] = dp[1][0][0][0][a] + reward : a bilo desno stavi go b desno
  c = next = tiffany[2]
  dp[1][a][c][0][b] = dp[0][0][a][0][b] + reward


    dp[at%2][left_bot][left_top][right_bot][right_top]

    MEM(dp, -inf)
    dp[0][0][0][0][0] = 0
    int ret = 0;
    for(int at = 0; at < n; at ++){
      for(int j = 0; j <= 3; j ++){
        for(int k = 0; k <=3 ; k++){
          for(int x = 0; x <= 3; x ++){
            for(int y = 0; y <= 3; y ++){
              int prev = at % 2;
              int now = 1 - prev;
              next = tiffany[at];
              ret = max(ret, dp[now][k][next][x][y] = max(dp[now][k][next][x][y], dp[prev][j][k][x][y] + reward(j, k, next)));
              ret = max(ret, dp[now][j][k][y][next] = max(dp[now][j][k][y][next], dp[prev][j][k][x][y] + reward(x, y, next)));
            }
          }
        }
      }
  	}


  #include <iostream>
#include <set>
#include <algorithm>
#include <map>
#include <cstring>
#include <fstream>
using namespace std;
int n;
string s;
struct node{
    int at, i1, i2, i3, i4;
    node(){}
    node(int &_at, int &_i1, int &_i2, int &_i3, int &_i4){
        at  =_at;
        i1 = _i1;
        i2 = _i2;
        i3 = _i3;
        i4 = _i4;
    }
    bool operator < (const node &a)const{
        if(at == a.at){
            if(i1 == a.i1){
                if(i2 == a.i2){
                    if(i3 == a.i3){
                        return i4 < a.i4;
                    }
                    return i3 < a.i3;
                }
                return i2 < a.i2;
            }
            return i1 < a.i1;
        }
        return at < a.at;
    }
};
// R - 0
// Y - 1
// G - 2
map<node, int> dp;
bool vis[10];
int rek(int &at, int &l1, int &l2, int &d1, int &d2){
    if(at == n){
        //  cout << "DA BE"<<endl;
        return 0;
    }
    int tmp = dp[node(at, l1, l2, d1, d2)];
    if(tmp != 0)return tmp;
    int ret = 0;
    int curr;
    vis[1] = vis[2] = vis[3] = false;
    if(s[at] == 'R'){
        curr = 1;
        vis[curr] = true;
    }
    else if(s[at] == 'Y'){
        curr = 2;
        vis[curr] = true;
    }
    else{
        curr = 3;
        vis[curr] = true;
    }
    if(l1 != 0){
        vis[l1] = true;
    }
    if(l2 != 0){
        vis[l2] = true;
    }
    int sz = 0;
    if(vis[1])sz ++;
    if(vis[2])sz ++;
    if(vis[3])sz ++;
    int newAt = at + 1;
    if(sz== 3){
        ret = max(ret, rek(newAt, l2, curr, d1, d2) + 3);
    }
    else if(sz == 2){
        ret = max(ret, rek(newAt, l2, curr, d1, d2) + 2);
    }
    else{
        ret = max(ret, rek(newAt, l2, curr, d1, d2) + 1);
    }
    vis[1] = vis[2] = vis[3] = false;
    vis[curr] = true;
    if(d1 != 0){
        vis[d1] = true;
    }
    if(d2 != 0){
        vis[d2] = true;
    }
    sz = 0;
    if(vis[1])sz ++;
    if(vis[2])sz ++;
    if(vis[3])sz ++;
    if(sz == 3){
        ret = max(ret, rek(newAt, l1, l2, d2, curr) + 3);
    }
    else if(sz == 2){
        ret = max(ret, rek(newAt, l1, l2, d2, curr) + 2);

    }
    else{
        ret = max(ret, rek(newAt, l1, l2, d2, curr) + 1);
    }
    return dp[(node(at, l1, l2, d1, d2))] = ret;
}
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);

//        ifstream cin("in.txt");
    cin >> n >> s;

    //    reverse(s.begin(), s.end());
    int t = 0;
    cout << rek(t, t, t, t, t) <<endl;
    return 0;
}

10 april popladne
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
#include <fstream>
using namespace std;

long long n, m, k;
const long long INF = 1e15;
vector<pair<long long, long long> > graph[100001];
long long cities[100001];
long long dist[100001];
bool visited[100001];
long long path[100001];
struct node{
    long long idx, cost;
    node(){}
    node(long long i, long long c){
        idx = i;
        cost = c;
    }
    bool operator < (const node &a)const{
        return cost > a.cost;
    }
};
long long ret;
bool put[100001];
bool imp[100001];
pair<long long ,long long> shotestCity(){
    for(int i = 0; i < n; i ++){
        dist[i] = INF;
        visited[i] = false;
    }
    priority_queue<node> q;
    dist[0] = 0;
    q.push(node(0, 0));
    node tmp;
    long long nxtNode, weight;
    while(!q.empty()){
        tmp = q.top();
        q.pop();
        if(visited[tmp.idx])continue;
        visited[tmp.idx] = true;
        for(long long i = 0; i < graph[tmp.idx].size(); i ++){
            nxtNode = graph[tmp.idx][i].first;
            weight = graph[tmp.idx][i].second;
            if(!visited[nxtNode] && tmp.cost + weight < dist[nxtNode]){
                dist[nxtNode] = tmp.cost + weight;
                q.push(node(nxtNode, tmp.cost + weight));
            }
        }
    }
    long long d = INF, id = -1;
    for(long long i = 0; i < k; i ++){
        if(imp[cities[i]] and dist[cities[i]] < d){
            d = dist[cities[i]];
            id = cities[i];
        }
    }
    return make_pair(d, id);

}
void dijkstra(long long A){
    for(int i = 0; i < n;i ++){
        visited[i] = false;
        path[i] = -1;
        dist[i] = INF;
    }
    dist[A] = 0;
    priority_queue<node> q;
    q.push(node(A, 0));
    node tmp;
    long long nxtNode, weight;
    while(!q.empty()){
        tmp = q.top()   ;
        q.pop();
        if(visited[tmp.idx])continue;
        visited[tmp.idx] = true;
        for(long long i  =0 ; i < graph[tmp.idx].size(); i ++){
            nxtNode = graph[tmp.idx][i].first;
            weight = graph[tmp.idx][i].second;
            if(!visited[nxtNode] && tmp.cost + weight < dist[nxtNode]){
                dist[nxtNode] = tmp.cost + weight;
                q.push(node(nxtNode, dist[nxtNode]));
                path[nxtNode] = tmp.idx;
            }
        }
    }
}
//bool vis[100001], v[100001];
long long sCity;
vector<pair<long long, long long> > newGraph[100001];
long long bfs(long long A){
    memset(visited, false, sizeof visited);
    queue<long long> q;
    q.push(A);
    visited[sCity]=  true;
    long long res = 0;
    while(!q.empty()){
        long long curr = q.front();
        q.pop();
        for(long long i =0 ; i < newGraph[curr].size(); i ++){
            long long nxtNode = newGraph[curr][i].first;
            long long weight = newGraph[curr][i].second;
            res = max(res, weight);
            if(!visited[nxtNode]){
                visited[nxtNode] = true;
                q.push(nxtNode);
            }
        }
    }
    return res;
}
bool vis[100001];
int main() {
    ios_base::sync_with_stdio(false);
    ifstream cin("in.txt");
    cin >> n >> m;
    long long a, b, c;
    for(long long i = 0; i < m; i ++){
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    cin >> k;
    memset(imp, false, sizeof imp);
    for(long long i = 0; i < k; i ++){
        cin >> cities[i];
        imp[cities[i]] = true;
    }
    pair<long long, long long> shortestCity = shotestCity();
    dijkstra(shortestCity.second);
     sCity = shortestCity.second;
    for(long long i = 0; i < k; i ++){
        long long A = sCity;
        long long B = cities[i];
        if(A != B){
            vector<long long> v;
            bool da = true;
            while(B != A){
                if(B == -1){
                    da = false;
                    break;
                }
                v.push_back(B);
                B = path[B];
            }
            v.push_back(A);
            if(da){
            reverse(v.begin(), v.end());
//            cout << cities[i] << endl;
            for(long long j = 0; j < v.size(); j ++){
                if(j < v.size() - 1){
                    newGraph[v[j]].push_back(make_pair(v[j + 1], dist[v[j + 1]]));
                    newGraph[v[j + 1]].push_back(make_pair(v[j], dist[v[j + 1]]));
                }
            }
            }
  //          cout<<endl;
        }
    }
    ret = 0;
    memset(vis, false, sizeof vis);
    for(long long i = 0; i < newGraph[sCity].size(); i ++){
        if(vis[newGraph[sCity][i].first])continue;
        vis[newGraph[sCity][i].first] = true;
        ret += bfs(newGraph[sCity][i].first);
    }
    cout << ret + shortestCity.first<< endl;

    return 0;
}
  Test case:


  Explanation from fb morning:
SAT 10:06PM
Ok
Btw ke ti se resetira visited
T.e ke treba da presmetash koi novodi se poblisku koga ke napravish reset na counterot

malce nejasno

znaci koga sme na node kaj koj treba da stavime stab
samo ja stavame tezinata na nodot

  a, b, c, d se gradovi. Treba da stavish shtabovi na a, c i d. Na primer ima pat od a=0 do b do c. Ima pat c - b - d kade shto. Ako dist(abd-cbd) > 0 => treba da go zemesh total_dist+=cdb. Odnosno treba nekoi nodovi da gi posetish dvapati.
Doobjasnuvanje: treba da stignesh do c i d za da stavish shtabovi
E sega treba da najdesh min(visit_in_order(c, d), visit in order (d, c)). E sega da vidime shto e visit_in_order(c, d): pocnuvash od 0 i odish do c pa do  d => odnosno odish ili dist (a=0, b, c) + dist (0, b, d) ili dist (a=0, b, c, b, d)

    a->b = a=0 b->cel pat do drugata strana
    b->c
    b->d
    total lenght = min({cost(a->b->c) + min(cost(a->b->d), cost(c->b->d))},
                       {cost(a->b->d) + min(cost(d->b->c), cost(a->b->c)})

mhmm
Ima smisla?
Vidi kako ja manipulirash visited nizata

pa ne bas
Koga stavash stigash do nekoj shtab i go resetirash dist counterot
*Koga stigash do nekoj shtab go resetirash dist counterot taka
Epa sega ako se vratish 1 node nazad od kade shto si doshol do toj shtab, togash dist do toj node stanuva dist(nodot od kaj doshol shtabot, nodot na shtabot), a predhodnata distanca za nodot od kaj shto si doshol do shtabot bila (0, nodot od kaj shto si doshol do shtabot). Eba sega imenuvaj go nodot od kaj shto si doshol do shtabot so imeto b. I napishi mi ja transformacinata shto ja objasnav pred dve recenici

dist[nxtNode] = dist[currNode]
dist[b] = dist[currNode]

6 7
2 3 135
0 3 898
0 4 480
3 5 295
2 4 262
0 1 216
2 5 682
2
2 1


  Josif's code for
http://mendo.mk/Task.do?id=381
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;

int n, m, k;
vector<pair<int, int> > graph[100001];
int cities[100001];
int dist[100001];
bool visited[100001];
int path[100001];
struct node{
    int idx, cost;
    node(){}
    node(int i, int c){
        idx = i;
        cost = c;
    }
    bool operator < (const node &a)const{
        return cost > a.cost;
    }
};
long long ret;
bool imp[100001];
void dijkstra(){
    memset(visited, false, sizeof visited);
    memset(dist, 63, sizeof dist);
    memset(path, -1, sizeof path);
    priority_queue<node> q;
    dist[0] = 0;
    q.push(node(0, 0));
    int nxtNode, weight;
    node tmp;
		bool is_void = true;
    while(!q.empty()){
        tmp = q.top();
        q.pop();
        if(visited[tmp.idx])continue;
        visited[tmp.idx] = true;
        if(imp[tmp.idx]){
          	//zoshto ovde da ne stavime
          	//memset(dist, 127, sizeof dist);<=
            ret += tmp.cost;
        	  tmp.cost = 0;
          	if(is_void)
            {
          			memset(dist, 127, sizeof dist);
              	is_void = false;
            }
        }
        for(int i =0; i < graph[tmp.idx].size(); i ++){
            nxtNode = graph[tmp.idx][i].first;
            weight = graph[tmp.idx][i].second;
            if(imp[tmp.idx]){
                if( dist[nxtNode] > weight){
                    dist[nxtNode] = weight;
                    q.push(node(nxtNode, weight));
                }
            }
            else{
                if(dist[nxtNode] > weight + tmp.cost){
                    dist[nxtNode] = weight + tmp.cost;
                    q.push(node(nxtNode, weight + tmp.cost));
                }
            }
        }
    }

}
bool vis[100001], v[100001];
vector<pair<int, int> > newGraph[100001];

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    int a, b, c;
    for(int i = 0; i < m; i ++){
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }

    cin >> k;
    memset(imp, false, sizeof imp);
    for(int i = 0; i < k; i ++){
        cin >> cities[i];
        imp[cities[i]] = true;
    }
    ret = 0;
    dijkstra();
    cout << ret << endl;

    return 0;
}


9 april sabajle
http://mendo.mk/Task.do?id=381


	0 1
  1 2
  0 3

  0 1 2 3

  0 - 1: 0 1
  0 - 2: 0 1 2
  0 ->3: 0 3




     0: 1, 3
    1 : 2

      Nov graf: poseti 1 3 4
      0 1 1
      1 2 2
      2 3 1
      3 4 2
      4 0 2

      0 1 1
        0: 4 1
          1 : 2
            2 : 3

              Visit: 0 5 8
              0 1 5
              0 2 1
              2 3 1
              3 4 1
              4 5 1
              5 6 3
              6 7 3
              7 8 3
              1 8 5

  po koj redosled gi posetuvame teminjata, rez = 0
           0 	Q.P(at = 0, d = 0)
           6	Q.P(at = 1, d = 5)
           1  Q.P(at = 2, d = 1)
           2  Q.P(at = 3, d = 2)
           3 	Q.P(at = 4, d = 3)
           4  Q.P(at = 5, d = 4) rez += 4
           5  Q.P(at = 6, d = 3)
           7  Q.P(at = 7, d = 6)
          	  Q.P(at = 8, d = 10)
              Q.P(at = 8, d = 9) rez+= 9
                break.

  #include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;

int n, m, k;
vector<pair<int, int> > graph[100001];
int cities[100001];
int dist[100001];
bool visited[100001];
int path[100001];
struct node{
    int idx, cost;
    node(){}
    node(int i, int c){
        idx = i;
        cost = c;
    }
    bool operator < (const node &a)const{
        return cost > a.cost;
    }
};
void dijkstra(){
    memset(visited, false, sizeof visited);
    memset(dist, 63, sizeof dist);
    memset(path, -1, sizeof path);
    dist[0] = 0;
    int nxtNode, weight;
    node tmp;
    priority_queue<node> q;
    q.push(node(0, 0));
    while(!q.empty()){
        tmp = q.top();
        q.pop();
        if(visited[tmp.idx])continue;
        visited[tmp.idx] = true;
        for(int i = 0; i < graph[tmp.idx].size(); i ++){
            nxtNode = graph[tmp.idx][i].first;
            weight = graph[tmp.idx][i].second;
            if(!visited[nxtNode] && tmp.cost + weight < dist[nxtNode]){
                dist[nxtNode] = tmp.cost + weight;
                q.push(node(nxtNode, dist[nxtNode]));
                path[nxtNode] = tmp.idx;
            }
        }
    }
}
bool vis[100001], v[100001];
vector<pair<int, int> > newGraph[100001];
int bfs(int node){
    queue<int> q;
    int curr;
    q.push(node);
    memset(v, false, sizeof v);
    v[node] = true;
    v[0] = true;
    int ret = 0;
    if(newGraph[0].size() > 0)
        ret = newGraph[0][node].second;
    while(!q.empty()) {
        curr = q.front();
        q.pop();
        for(int i =0; i < newGraph[curr].size(); i ++){
            if(!v[newGraph[curr][i].first]){
                v[newGraph[curr][i].first] = true;
                q.push(newGraph[curr][i].first);
                ret = max(ret, newGraph[curr][i].second);
            }
        }
    }
    return ret;
}
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    int a, b, c;
    for(int i = 0; i < m; i ++){
        cin >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, c));
    }
    cin >> k;
    for(int i = 0; i < k; i ++){
        cin >> cities[i];
    }
    dijkstra();
    int A, B;
    for(int i = 0; i < k; i ++){
        B = cities[i];
        A = 0;
        vector<int> v;
        bool da = false;
        while(B != A){
            if(B == -1){
                da = true;
                break;
            }
            v.push_back(B);
            B = path[B];
        }
        v.push_back(A);
        reverse(v.begin(), v.end());
        if(v.size() > 1 && !da){
            for(int j = 0; j < v.size() - 1; j ++){
                newGraph[v[j]].push_back(make_pair(v[j + 1], dist[v[j + 1]]));
                //   newGraph[v[j + 1]].push_back(make_pair(v[j], dist[v[j]]));

            }
        }
    }
    //cout << dist[1] << " " << dist[2] << endl;
    vector<pair<int, int> >::iterator it;
    memset(vis, false, sizeof vis);
    vis[0] = true;
    long long ret = 0;
    for(int i =0; i <newGraph[0].size(); i ++){
        int t = newGraph[0][i].first;
        if(!vis[t]){
            vis[t] = true;
            ret += max(newGraph[0][i].second, bfs(t));
            //     cout << bfs(t) << endl;
        }
    }
    // vis[0] = true;
    cout << ret << endl;

    return 0;
}




# classes is a list of tuples [(g_1, b_1), (g_2, b_2), ... , (g_{n-1}, b_{n-1})] (see handout for definitions).
# T is some positive number.
def inefficient_allocate_time(classes, T):
    time_allocated = 0
    total_benefit = 0

    while time_allocated < T:
        # Find which remaining class would be best to allocate our time to.
        best_ratio = -float('inf')
        best_i = -1
        for i, (goal, benefit) in enumerate(classes): # O(n)
            if benefit/goal > best_ratio:
                best_ratio = benefit/goal
                best_i = i

        if best_i == -1:
            # If we run out of classes, return.
            return total_benefit

        # Allocate as much time as we can to the best class found.
        goal, benefit = classes[best_i]
        # We can't go over our limit T or over the goal limit for this class.
        time_to_allocate = min(T - time_allocated, goal)
        time_allocated += time_to_allocate
        total_benefit += benefit/goal * time_to_allocate

        # We can't allocate any more time to this class, so delete it.
        del classes[best_i] # O(n)
    return total_benefit

def allocate_time(classes, T):
    return inefficient_allocate_time(classes, T)
Mart 28mi, nedelata pred drzaven

Tuka si?
  da
  Josif?

  dada
  tuka sum


  Top, epa sledi sea

    vo kodov ovde
   add zavisi od tmpMask i at
    se drugo e konstantno
    taka da moze da se zapishe short int add_memo[_neshto_][_neshto_], kade shto ke zapisheme stvari od precompute-ot

    Josif:
    aham znaci cim se drugo e konstanto
      add_memo[at][bitmask]

      				Kliment: Check :D xD

Kliment:
Oh, Ova e top, ke moze da pishuvame rekurentnti muabeti
  ke mozam da ti posocuvam vo koja linija imam objasnato nekoj koncept
  i posle ke moze da gi upotrebime muabetive da napisham kniga za zadaci za natprevari po matematika
  xD
  Ova ke e top :D
    Josif:
    	ahahahahahaahha dada
        Kliment:
  					Ok, se vrakjame na rabota.
            goto: "Code to precompute"
    sledam
    Sledi:
"Code to precompute"
As global variable:
short int add[21][1<<20];
  uu ama dali ke iame dovolno memorija
    poso dpto ke ni bide 40mb

    Kliment: neznam
      moment da vidam
      napraj mi ubedliv argument zoshto ke padne
          Josif:
          aham sea
          20 * (2^20) * sizeof(short int) / 1024 / 1024
          20 * (2^20) * 2 / 1024 / 1024 = 40mb


          Kliment:
							Okej, fer, znaci ke treba da najdeme nacin kako da koristeme memmorija na rolling basis.
              Kao, da ne ja cuvame celata
                msm deka nema potreba da praime precompute na add_cost, dovolno e na maskite samo
                  ili pa nesto kako knapsack od kraj koga pustame
                  samo dp[at] bez bitmaskata ili samo dp[bitmask]
                  aha fer vidi go ova: edinstveni opcii za bitmaski ni se tie so 1 bit aktiven, ili tie so n aktivni bitovi na edna grupa na objekti so ist label.
                                                                              na primer:  1000    GOTO "CONTINUE BITCOUNT"

                                                                                          0100
                                                                                          0010
                                                                              						0001
"CONTINUE BITCOUNT"
na primer ako imame grad so zgradi 1233323 izbor ni se
  moze da cuvame mapa
  dp da ni e mapa

    Kliment: Aha, pa da, ke treba toa da go imame, ali pak togash ke imame
      O(log(2^20)*2^20)) = O(20*2^20). I O(log(2^20)) = O(20),
			shto ke ni e potrebno vo sekoja rekurzija O(20) pati. Thus
    , pak imash O(2^n*n^3) vreme.
      ama samo ednas ke bide taa 20ka
      znaci ke bide n^2 sam

      Kliment: ama vikam deka za da izvadish element od mapata, treba da upotrebish operacija find() vo mapa so 2^20 elementi.
        taa e log2
        aa dadada
        jasno
        ama pak ke bide 20*20
        epa sekoja reurzija ke ima

        da i Log2(2^20) = 20. toa e deficinijata na log2.
        i imash O(log2(2^20)) = O(20) operacii sekoj pat koga sakash da pristapish do add_memmo (taka ke ni se vika dpto).
        , a sakash da pristapish vo add_memmo 20 pati vo sekoja rekurzija, a imash 20*2^20 rekurzii, taka da broish O(2^20*20^3) :D :D :D
          kako zvuci toa?
          aham jasno , ja mislev samo dpto da ni bide mapa.
            Kliment: Pa istiot problem ke go imash.
              dada
              jasno jasno
              a kako ke go sredime ova bez mapa
              ako koristish mapa, koristish log faktor taka da ke imash nesshto O(neshto*log(2^20)) deka 2^20 ti se moznite bitovi.
                , a toa e O(neshto_podobreno*20)
                A tvoeto neshto_podobreno e O(20*20*\

                                    inc moeto ne pagase na vreme
                                    2^20), a se vika neshto_podobreno deka e podobruvanje od 20*20*20*2^20. Odnosno so cel da go napravish podobruvanjeto ti samo izrazuvash drug nacin kako da ja imash istata kompleksnost. :D :D :D Kako zvuci toa?

City: 12232334444
  		1______
            ama ne mi padna na vreme
                  za pogresen rezultat dava
                  poso ne mi e dobra formulata
                  inc mn ginc mn e sporo codeshare ____

short int f(1__________) = 10000000:
se zaglavi codeshare ne sledev
  sto se desava sea
  klimetnt?
short int f(_______1000) = 00000000:
short int f(_______0100) = 00000000:
short int f(_______0010) = 00000000:
short int f(_______0001) = 00000000:
short int f(_______1111) = 00000000:
short int f(_______0011) = 00000000:
short int f(_______0101) = 00000000:
short int f(_______1010) = 00000000:
short int f(_______1010) = 00000000:
short int f(_______1100) = 00000000:
short int f(_10_0______)
short int f(_01_0______)
short int f(_00_1______)
short int f(_11_1______)
  similar for ___3_33____



short int add = val[at];
short  int exp = 0;
tmpMask |= bitmask;
short int newnew = tmpMask;

while(newnew){
  if(newnew % 2 == 1){
      add -= cost[exp][at];
  }
  newnew /= 2;
  exp ++;
}
ret = min(ret, rek(at + 1, tmpMask) + add);
if(i == n - 1){
  ret = min(ret, rek(at + 1, tmpMask) + add);
}

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
#include <assert.h>
#define MAX 1<<15
#define MAXN 20
using namespace std;
short int n, m;
short int type[MAXN+1][MAXN+1];
short int cost[MAXN+1][MAXN+1];
short int dp[MAXN+1][1<<MAXN];
short int all_of_type_make_unique[MAXN+1][MAXN+1];
int all_of_one_type[MAXN+1][MAXN+1];
short int bp[1<<MAXN];

int min(int a, int b)
{
    if(a<b)
    {
        return a;
    }
    return b;
}

bool check_bit(const int bit, const short int at)
{
    return ((bit&(1<<at))!=0);
}
short int rek(const short int at, const int bitmask){
    if(bp[bitmask] == n){
        return 0;
    }
    if(at == m){
        return MAX;
    }

    if(dp[at][bitmask]!= -1){
        return dp[at][bitmask];
    }
    short int ret =  MAX;
    for(short int i = 0; i < n; i ++){
        if(!check_bit(bitmask, i))
        {
            ret = min(ret, rek(at, bitmask|(1<<i))+cost[i][at]);
            ret = min(ret, rek(at, bitmask|all_of_one_type[i][at])+all_of_type_make_unique[i][at]);
        }
    }
    ret = min(ret, rek(at+1, bitmask));

    return dp[at][bitmask] = ret;
}
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    for(short int i = 0; i < n; i ++){
        for(short int j = 0; j < m; j ++){
            cin >> type[i][j];
        }
    }
    for(short int i = 0; i < n; i ++){
        for(short int j = 0; j < m; j ++){
            cin >> cost[i][j];
        }
    }
    for(short int at=0;at<m;at++)
    {
        short int vis = 0;
        for(short int i=0;i<n;i++)
        {
            if(check_bit(vis, i))
            {
                continue;
            }
            int tmp_all_of_one_type = 0;
            short int sum = 0;
            short int max_price = 0;
            for(short int j = 0; j < n; j ++){
                if(type[i][at] == type[j][at]){
                    vis|=(1<<j);
                    tmp_all_of_one_type |= (1 << j);
                    sum+=cost[j][at];
                    max_price = max(max_price, cost[j][at]);
                }
            }
            for(short int j = 0; j < n; j++)
            {
                if(type[i][at] == type[j][at])
                {
                    assert(tmp_all_of_one_type != 0);
                    all_of_one_type[j][at] = tmp_all_of_one_type;
                    all_of_type_make_unique[j][at] = sum-max_price;
                }
            }
        }
    }
    for(int i=0;i<(1<<MAXN);i++)
    {
        bp[i] = __builtin_popcount(i);
    }
    memset(dp, -1, sizeof dp);
    cout << rek(0, 0)    << endl;
    return 0;
}
/*
 4 3
 1 2 1
 3 2 2
 3 1 2
 1 1 1
 50 30 60
 20 40 50
 30 30 30
 40 40 30

5 1
7
2
7
7
30
61
61
61
61
61
*/




26ti mart nedela pred drzaven

guides: 0 1 2 3 4 5... 100
participants: 0 1 2 ... 14

guide     bitmask of participants
	0
  1
  2
  3
  4
  5

#guides: 3, #countries: 2



rez = sum_for_all_i(column_i) - sum_for_each_i_choose_one_j(a_i_j)

  minimize rez => maximize sum_for_each_i_choose_one_j(a_i_j)
  i -> country
  j -> guide

  int dp[100][1<<15];
	int sum[]
    for(i -> n)
    for(j -> m)
    sum[j] += mat[i][j]
    for(i)
    for(j)
    cost[i][j] = sum[j] - mat[i][j];

	dp[guide_j][bit] = rez;
	ni pretstavuva koi drzavi vo bit se zemeni od site guides pomegju 0 <=guides<= j;
  rek(at, bitmask)
    tmp  = bitmask
    while(tmp)
    if(tmp % 2 == 0)
    for_each_bit_which_is_zero_in_the_bitmask
    rek(at,bitmask) = min(rek(at + 1, bitmask + (1 << bit) + sum_for_all[at][bit])

    for(int i=0;i< num_countries;i++)
    {
      if((bit&(1<<i))==0)
      {
        int newBit = bit+(1<<i);
        int cost = sum[guide_at];
        cost -= input_mat[guide_at][i];
        ret = min(ret, rek(at+1, newBit)+cost);
      }
    }



  			  country_i
  guide_j a_ij




  4 <- sum(column) - 4
  5
  6
  1
  2




      0 1
  0 : 0 16
  1 : 0 0
  2 : 0 0

	4 + 1 =  5

/* Code written by Kliment Serafimov */

#include <fstream>
#include <iomanip>
#include <iostream>

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>

#define P push
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define DEC 0.00000001
#define MAX 2139062143
#define MAX_63  1061109567
#define MAXll 9187201950435737471
#define bp(a) __builtin_popcount(a)
#define rand(a, b) ((rand()%(b-a+1))+a)
#define MEM(a, b) memset(a, b, sizeof(a))
#define sort_v(a) sort(a.begin(), a.end())
#define rev_v(a)  reverse(a.begin(), a.end())

//#define fin cin
//#define fout cout
using namespace std;
//ifstream fin(".in");
//ofstream fout(".out");

#define set_bit(A,bit) (A|=(1<< (bit)))
#define clear_bit(A,bit) ((A&=~(1 << (bit))))
#define test_bit(A,bit) ((A&(1<<bit))!=0)
#define print_bits(A,n) for(int BIT=0;BIT<n;BIT++)cout<<test_bit(A,BIT);
#define print_bits_endl(A,n) for(int BIT=0;BIT<n;BIT++)cout<<test_bit(A,BIT);cout<<endl;
int ma[101][16];
int dp[101][1<<15];
int sum[15];
int n, m;
int rek(int at, int bit)
{
    if(dp[at][bit]!=-1)
        return dp[at][bit];
    if(bp(bit)==m)
        return 0;
    if(at==n)
        return MAX;
    int ret = MAX;
    for(int i=0;i<m;i++)
    {
        if(!test_bit(bit, i))
        {
            int newBit = bit;
            set_bit(newBit, i);
            int val = rek(at+1, newBit);
            val+=sum[i]-ma[at][i];
            ret = min(ret, val);
        }
    }
    ret = min(ret, rek(at+1, bit));
    dp[at][bit] = ret;
    return ret;
}
int main()
{
    cin >> n >> m;
    MEM(sum, 0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> ma[i][j];
            sum[j]+=ma[i][j];
        }
    }
    MEM(dp, -1);
    cout << rek(0, 0);
    return 0;
}

26 feb. 2017 nedelata pred regionalen (superstring + backtrack)

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <fstream>
using namespace std;
int n;
int arr[10001];
vector<pair<int, int> > vals;
vector<pair<int, int >> c;
int mymerge(int a, int b){
    return max(a, b);
}
class node{
public:
    int val;
    node *left, *right;
    int leftBound, rightBound;
    bool doPush = false;
    node(int levo, int desno){
        leftBound = levo;
        rightBound = desno;
        if(levo == desno){
            val = arr[levo];
        }
        else{
            int mid = (levo + desno) / 2;
            left = new node(levo ,mid);
            right = new node(mid + 1, desno);
            val = mymerge(left -> val, right -> val);
        }
    }
    int updateVal(int old, int newVal){
        return newVal;
    }
    void setLazyMarker(int newVal){
      val =  updateVal(val, newVal);
        if(leftBound != rightBound){
            doPush = true;
        }
    }
    void pushLazyMarker(){
        if(doPush){
            doPush = false;
            left -> setLazyMarker(val);
            right -> setLazyMarker(val);
        }
    }
    void update(int i, int j, int newVal){
        if(i <= leftBound && rightBound <= j){
            setLazyMarker(newVal);
        }
        else if(j >= leftBound && rightBound >= i){
            pushLazyMarker();
            left -> update(i, j, newVal);
            right -> update(i, j, newVal);
            val = mymerge(left -> val, right -> val);
        }


    }
    int query(int i, int j){
        pushLazyMarker();
        if(i <= leftBound && rightBound <= j){
            return val;
        }
        if(rightBound < i)return 0;
        if(j < leftBound)return 0;
        return mymerge(left -> query(i, j), right -> query(i, j));
    }

};
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    memset(arr, 0, sizeof arr);
    node segmentTree(0, n - 1);
    for(int i = 0; i < n; i ++){
        cin >> arr[i];
        vals.push_back(make_pair(arr[i], i));
    }
    sort(vals.begin(), vals.end());
    for(int i = 0; i < n; i ++){
        c.push_back(make_pair(vals[i].second, i));
    }
    sort(c.begin(), c.end());
    int ret = 0;
    int dptmp;
    segmentTree.update(c[0].second, c[0].second, 1);
    for(int i = 1; i < n; i ++){
        dptmp = segmentTree.query(0, c[i].second - 1) + 1;
        segmentTree.update(c[i].second, c[i].second, dptmp);
        ret = max(dptmp, ret);
    }
    cout << ret << endl;
    //10 22 9 33 21 50 41 60
    return 0;
}


-----------------------------------
             [   ]
at:          0  1 2 3
mcs:         1  2< 2
arr:         2 20 4 3 6 12  8  4 10

id :         0  1 2 3 4  5  6  7  8
v.f:         2  3 4 4 6  8 10 12 20
v.s:         0  3 2 7 4  6  8  5  1

c.f: (=v.s)  0  3 2 7 4  6  8  5  1
c.s: (= id)  0  1 2 3 4  5  6  7  8

sort(c)


             [  ]
at:          0 1 2 3 4 5 6 7 8
mcs:         1

c.f: (=v.s)  0 1 2 3 4 5 6 7 8
c.s: (= id)  0 8 2 1 4 7 5 3 6

r.update(c[0], 1);
at:          0 1 2 3 4 5 6 7 8
mcs:         1
for(int at = 1; at<n; at++)
{
    int dp_at = r.query(0, c[at].s-1)+1;

    query(at=1)  r.query(0, c[at].s-1) = 1
    at:          0 1 2 3 4 5 6 7 8
    mcs:        [1              ]

    query(at=2) r.query(0, c[at].s-1) = 1
    at:          0 1 2 3 4 5 6 7 8
    mcs:        [1  ]            2

    query(at=3) r.query(0, c[at].s-1) = 1
    at:          0 1 2 3 4 5 6 7 8
    mcs:        [1]2             2

    query(at = 4) r.query(0, c[at].s-1) = 2
    at:          0 1 2 3 4 5 6 7 8
    mcs:        [1 2    ]        2

    r.update(c[at].s, dp_at); // update na pozicija c[at].s stavi vrednost ret

    update(at=1)      r.update(c[at].s, dp_at)
    at:               0 1 2 3 4 5 6 7 8
    mcs update(at=1)  1               2

    update(at=2)      r.update(c[at].s, dp_at)
    at:               0 1 2 3 4 5 6 7 8
    mcs update(at=1)  1 2             2

    update(at=3)      r.update(c[at].s, dp_at)
    at:               0 1 2 3 4 5 6 7 8
    mcs update(at=1)  1 2 2           2

    update(at=4)      r.update(c[at].s, dp_at)
    at:               0 1 2 3 4 5 6 7 8
    mcs update(at=4)  1 2 2   3        2

    ret = max(ret, dpedit.com/sh8r


19th March, lenght: 1:43
Longest altrnating subsequence
              id:    0 1 2 3 4 5
    segmenttree1:    0 0 0 1 0 0
    segmenttree2:    0 0 0 1 0 0
    Arr              3 5 4 2 0
    st1 : arr[i] = 3 :  segmenttree1.update(arr[i], segmenttree2.query(0, (array[i]-1 = 2)) + 1)
    st2 : arr[i] ->     segmenttree2.update(arr[i], segmenttree1.query(arr[i]+1 = 4, 5) + 1
    arr[i] = 5

    LAS(a, b) = LAS(0, b) - LAS(0, a-1);
     [         ]
    0 1 2 3 4 5
    3 3 5 4 7 1

     1 2 3 4 5 6 7 8 9

    [  ]
    update at
    position = 5
    update(5, x):
    case 1: x <= arr[4]; x = 0 delta = 0
    case 2: x >= arr[6]; x = 8 delta = 2
    case 3: arr[4] < x < arr[6] delta = 0

      /  \    /    \ /     \
              U
    0 1 2 3 4 5 6 Ta7 8 9 10 111213

    [   ]   [ ] [ ] [    ]      -> continuous increasing subsequences
    3 4 5 2 1 8 7 8 6 9 10 4 3 2
        [   ] [ ] [ ]    [     ]-> continuous decreasing subsequences

*
    0 1 2 3 4 5 6 7 8 9 10 11 12 13
*       *   * * * * *    *
]:  2 2 4 4 4 5 7
    3 4 5 2 1 8 7 8 6 9 10  4  3  2
[:  0 0 0 2 2 4 6
   pre - upadte
   LAS(0, 13) = {3, 5, 1, 8, 6, 10, 2}

   post update:
   LAS(0, 13) = {3, 5, 1, 8, 7, 8, 6, 10, 2}

   if(arr[at] == 7 && prev == 'small' ) next = "on right of 8"

   if(arr[at] == 7 && prev == 'big'   ) next = "on left or equal to 8"

     1 2 3 4 5
   [ o l x r ][o][ o o o o ]

     1  2  1  4   5
   [ o [l][xhhbg] r ][o][ o o o o ]  if(x<l)

      1 2  5   4   5
     [o l [x] [r] [o] o o o o ] if(x>r)


  [ o o o l [x] r o o o ] if(x> max(l, r))

    [ o o o [l] [x] [r] o o o ] if(x< max(l, r))

  count_*(0, a) runs in O(log n)

   LAS(a, b) = count_*(0, b) - count_*(0, a-1) + c
   c = (a != * + b != *)
     [  []   []   [][] ]
     a                 b
   [    []   []   [][]    []   []   ]

#include <bits/stdc++.h>

using namespace std;
int n, q;
int arr[200001];
int a, b;
class element
{
public:
    int val;
    bool isLeftInc, isRightInc;
    int left_mono_size, right_mono_size; //mono - monoton increasing/decreasing
    int size;
    int leftestElement;
    int rightestElement;
    element(int e)
   {
       val = 0;
       isLeftInc = isRightInc = true;
       left_mono_size = right_mono_size = 1;
       size = 1;
       leftestElement = e;
       rightestElement = e;
   }
   element(element *x, element *y)
   {
       val = x->val+y->val;
       size = x->size+y->size;
       leftestElement = x->leftestElement;
     	 rightestElement = y->rightestElement;
     		// x = 2, y = 1;
       if(x->size == x->left_mono_size) // all of x is monoton
       {
           assert(x->isRightInc);
           assert(x->right_mono_size == x->size)
           if(y->size == y->left_mono_size) // all of y is monoton
           {
               assert(y->isRightInc);
               assert(y->right_mono_size == y->size);
               if(x->isLeftInc == y.isLeftInc) // if x and y are monoton in the same way x = 123 y = 234
               {
                 if(x->isLeftInc && x->rightestElement<y->leftestElement)// x = 123, y = 456
                 {
                   isLeftInc = isRightInc = x->isLeftInc;
                   left_mono_size = right_mono_size = size;
                 }
                 else if(!x->isLeftInc  &&  x->rightestElement>y->leftestElement)// x = 654 y = 321
                 {
                   	isLeftInc = isRightInc = x->leftInc;
                    left_mono_size = right_mono_size = size;
                 }
                 else // x = 123 y = 234 OR x = 654 y = 543
                 {
                   //current node : xy; left part of curr node = x, right part is y
                   	isLeftInc = x->isLeftInc; // because we know that x->isLeftInc = x->isRightInc because x->size == x->left_mono_size == x->right_mono_size
                    isRightInc = y->isRightInc;
                   	left_mono_size = x->size; // x->size = x->left_mono_size;
                   	right_mono_size = y->size; // y->size = y->right_mono_size;
                   	val =
                 }

               }
               else // if x and y are monoton in different ways;
               {
                   isLeftInc = x->isLeftInc;
                   left_mono_size = x->size;
                   isRightInc = y->isRightInc;
                   right_mono_size = y->size;
               }
           }
       }

}
bool b1, b2;
class node{
    public:
    int leftBound, rightBound;
    node *left, *right;
    element val;
    node(int levo, int desno){
        leftBound = levo;
        rightBound = desno;
        if(levo == desno){
            val = element(arr[levo]);
            return;
        }
        else{
            int mid = (levo + desno) / 2;
           left = new node(levo, mid);
           right = new node(mid + 1, desno);
           val = element(&(left -> val), &(right -> val));
        }
    }
    void update(int _node, int newVal){
        if(leftBound == rightBound){
            val = newVal;
            return;
        }
        int mid = (leftBound + rightBound) / 2;
        if(_node >= right -> leftBound){
            right -> update(_node, newVal);
        }
        else if(_node <= left->rightBound){
            left -> update(_node, newVal);
        }
        val = mymerge(left -> val, right -> val);
    }
    int query(int i, int j){
        if(i <= leftBound && rightBound <= j){
            return val;
        }
        if(rightBound < i)return 0;
        if(j < leftBound)return 0;
        return mymerge(left->query(i, j), right->query(i, j));
    }
};
struct interval{
    int first, second;
    interval(){}
    interval(int f, int s){
        first = f;
        second = s;
    }
};
bool star[200001];
int main()
{
    ios_base::sync_with_stdio(false);
 //   ifstream cin("in.txt");

    cin >> n >> q;
    //cin >> q;
    int mxx = 0;
    vector<interval> v;
    for(int i = 0; i < n; i ++){
        cin >> arr[i];

    }
    int it1 = 0, it2 = 0;
    bool inc = false, dec = false;
    if(arr[1] > arr[0])inc = true;
    else dec = true;
    arr[n] = arr[n - 1];
    memset(star, false, sizeof star);
    for(int i = 1; i <= n; i ++){
        if(inc){
            if(arr[i] > arr[i - 1]){
                it2 = i;
            }
            else{
           // it2 = i - 1;
                star[i - 1] = true;
                v.push_back(interval(it1, i - 1, false));
                it1 = i-1 ;
                inc = false;
                dec = true;
            }
        }
        else{
            if(arr[i] < arr[i - 1]){
                it2 = i;
            }
            else{
                //it2 = i;

                star[i - 1] = true;
                v.push_back(interval(it1, i - 1));
                it1 = i -1;
                inc = true;
                dec = false;
            }
        }
    }

    cout << endl;
    star[n - 1] = false;
    node segmentTree(0, n - 1);
    for(int i = 0; i < n; i ++){
        if(star[i]){
       //   cout << i << " " ;
            segmentTree.update(i, 1);
            continue;
        }
    }
   // cout << endl;
  //  cout << segmentTree.query(0, 0) << endl;
   // cout << "INPUT NUMBER OF QUERIES: ";

            string tmp;

    for(int i =0; i < q ; i++){
        cin >> tmp;
        cin >> a >> b;
        if(tmp == "COUNT"){
            a --;
            b --;
            cout << (b - a + 1) - ((!star[a] + !star[b]) + (segmentTree.query(0,b)-segmentTree.query(0,a-1))) << endl;
        }
        else{
            a --;
            arr[a] = b;


        }

    }
    return 0;
}
/**/


intv:       [            ]
root: --------------------------
r.l:  ----------12
r.r:              343-----------
r.r.l             343-----
r.r.r                     ------

--------

class node
{
public:
    int lb, rb;
    node* leftchild, rightchild;
    bool is_left_inc, is_right_inc;
    int val;
    node(int levo, int desno)
    {
        lb = levo;
        rb = desno;
        if(levo == desno){

        }

    }
}

  1 2 3

  +1 +1
  [  [ ]  ]
  1 2 3 2 1
  [+1 +1] [-1 -1]

  5 4 5 4
   -1 +1 -1

take: 2   2   2      2   222
	   ++++----+++++++-----+-+
      2   +1  +1     +1  +1+1+1  =


/* Code written by Kliment Serafimov */

#include <fstream>
#include <iomanip>
#include <iostream>

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>

#define P push
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define DEC 0.00000001
#define MAX 2139062143
#define MAX_63  1061109567
#define MAXll 9187201950435737471
#define bp(a) __builtin_popcount(a)
#define rand(a, b) ((rand()%(b-a+1))+a)
#define MEM(a, b) memset(a, b, sizeof(a))
#define sort_v(a) sort(a.begin(), a.end())
#define rev_v(a)  reverse(a.begin(), a.end())

//#define fin cin
//#define fout cout
using namespace std;
//ifstream fin(".in");
//ofstream fout(".out");

#define set_bit(A,bit) (A|=(1<< (bit)))
#define clear_bit(A,bit) ((A&=~(1 << (bit))))
#define test_bit(A,bit) ((A&(1<<(bit)))!=0)

vector<int> arr;
class element
{
public:
    int val;
    int is_monoton;
    int left_inc;
    int right_inc;
    element(int l, int r)
    {
        val = 0;
        is_monoton = true;
        left_inc = right_inc = l<r;
    }
    element(string s)
    {
        assert(s == "empty");
        val = -1;
    }
    element(element *x, element *y)
    {
        if(x->val == -1 && y->val == -1)
        {
            assert(0);
        }
        if(x->val == -1)
        {
            val = y->val;
            is_monoton = y->is_monoton;
            left_inc = y->left_inc;
            right_inc = y->right_inc;
        }
        else if(y->val == -1)
        {
            val = x->val;
            is_monoton = x->is_monoton;
            left_inc = x->left_inc;
            right_inc = x->right_inc;
        }
        else if(x->is_monoton && y->is_monoton) //x = 123, y = 345 oR x = 123, y = 321
        {
            if(x->left_inc == y->left_inc)
            {
                is_monoton = true;
                left_inc = right_inc = x->left_inc;
                val = 0;
            }
            else
            {
                is_monoton = false;
                left_inc = x->left_inc;
                right_inc = y->left_inc; // y->left_inc = y->right_inc
                val = 1;
            }
        }
        else
        {
            is_monoton = false;
            left_inc = x->left_inc;
            right_inc = y->right_inc;
            val = x->val+y->val+(x->right_inc!=y->left_inc);
        }
    }
    element()
    {

    }
};

class node
{
public:
    int lb, hb;
    node *leftChild, *rightChild;
    element val;
    node(int left, int right)
    {
        lb = left;
        hb = right;
        if(lb == hb)
        {
            val = element(arr[lb], arr[lb+1]);
        }
        else
        {
            int mid = (lb+hb)/2;
            leftChild = new node(lb, mid);
            rightChild = new node(mid+1, hb);
            val = element(&(leftChild->val), &(rightChild->val));
        }
    }
    void update(int idx)
    {
        if(lb == hb)
        {
            val = element(arr[idx], arr[idx+1]);
            return;
        }
        if(idx >= rightChild->lb)
        {
            rightChild->update(idx);
        }
        else
        {
            leftChild -> update(idx);
        }
        val = element(&(leftChild -> val), &(rightChild -> val));

    }
    element *query(int l, int r)
    {
        if(l<=lb && hb <= r)
        {
            return &val;
        }
        else if(hb<l || r<lb)
        {
            return new element("empty");
        }
        else
        {
            return new element((leftChild->query(l, r)), (rightChild->query(l, r)));
        }
    }
    node(){}
}root;


int main()
{
    int n;
    int q;
    cin >> n >> q;

    for(int i=0; i<n; i++)
    {
        int a;
        cin >> a;
        arr.pb(a);
    }
    cout << endl;
    root = node(0, n-2);

    for(int i; i<q; i++)
    {
        string type;
        cin >> type;
        if(type == "REPLACE")
        {
            int at, e;
            cin >> at >> e;
            at--;
            arr[at] = e;
            if(at!=0)
                root.update(at-1);
            root.update(at);
        }
        else if (type == "COUNT")
        {
            int l, r;
            cin >> l >> r;
            l--, r--;
            cout << (r-l+1)-(root.query(l, r-1)->val+2) <<endl;
        }
        else
        {
            assert(0);
        }
    }
    return 0;
}