// ...
#if not LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
std::vector<int> positions; // it's more convenient to make it global. It's not changed very frequently anyway
/*
* stores a convex piecewise linear function.
* the cuts must be in positions.
*/
struct Tree{
using Data=std::array<int64_t, 2>; // sort of parallel data tuple. Can be used for anything.
std::vector<Data> data; // "lazy"
Tree(std::size_t number): data(number*2){}
static void add1(Data& first, Data sec){
first[0]+=sec[0];
first[1]+=sec[1];
}
int offset() const{return int(data.size()/2);}
// get raw {a, b} value at a particular position.
Data rawGet(int index)const{
index+=offset();
Data result{};
for(; index; index>>=1)
add1(result, data[index]);
return result;
}
// add a value to a range.
void add(int left, int right, Data const value){
left+=offset(); right+=offset();
assert(left<=right);
while(left<right){
if(left&1) add1(data[left++], value);
if(right&1) add1(data[--right], value);
left>>=1; right>>=1;
}
}
// self explanatory.
int64_t getAtIndex(int index)const{
auto const [a, b]=(*this).rawGet(index);
return (int64_t)a*positions[index]+b;
}
// get the function value, at a particular (possibly not in positions) position.
int64_t getAtValue(int value)const{
// interpolate if necessary. (always work in this particular problem...)
// could be a little simpler (by explicitly store the slope on each segment), but...
// :(
auto const iterator=std::lower_bound(begin(positions), end(positions), value);
int64_t const value2=getAtIndex(int(iterator-positions.begin()));
if(*iterator==value) return value2;
int64_t const value1=getAtIndex(int(iterator-positions.begin())-1);
auto const number=value1*(*iterator-value)+value2*(value-iterator[-1]);
auto const de=*iterator-iterator[-1];
assert(number%de==0);
return number/de;
}
// get any index for which getAtIndex returns the minimum value.
int minIndex() const{
// assumes some specific kind of function shape.
// currently O(log^2 n)
// could be O(log n) instead.
// :(
// the boundary binary search might be reducible to O(log n)
// too with some careful planning. I don't know.
auto const value=[&](int pos){
assert(0<=pos and pos<offset());
return (*this).rawGet(pos)[0];
};
int pos=offset();
for(int step=1<<30; step>>=1;){
if(pos-step>=0 and value(pos-step)>=0) pos-=step;
}
// now pos=first element with value >=0
std::pair<int64_t, int> result{INT64_MAX, INT_MAX};
for(int pos1=pos-1; pos1<=pos; ++pos1){ // perhaps this can be simpler? I don't know...
if((unsigned) pos1<(unsigned)offset())
result=std::min(result, std::make_pair(getAtIndex(pos1), pos1));
}
assert(([&]{ // (slow) ensure that the found index is really the minimum.
for(int pos1=0; pos1<offset(); ++pos1){
assert(getAtIndex(pos1)>=result.first);
}
return true;
}()));
return result.second;
}
};
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
int k, number; std::cin>>k>>number;
if(k==1) return 1;
int64_t result{};
std::vector<std::array<int, 2>> queries;
// read into queries, and prepare result (nonoptimizable part).
// this part should not be wrong.
for(int _=0; _<number; ++_){
char a, b; int first, sec;
std::cin>>a>>first>>b>>sec;
if(first>sec) std::swap(first, sec);
result+=sec-first; // minimum required
if(a!=b){
result+=1; // need to cross a bridge anyway
queries.push_back({first, sec});
positions.push_back(first); positions.push_back(sec);
}
}
number=-1;
if(queries.empty()){
std::cout<<result<<'\n';
return 0;
}
// sort positions.
std::sort(begin(positions), end(positions));
positions.erase(std::unique(begin(positions), end(positions)), end(positions));
// from now on, positions are not changed anymore.
auto minAdd=INT64_MAX;
// minimum of the function (it's hard to explain.)
std::sort(begin(queries), end(queries), [&](auto const& first, auto const& sec){
return first[0]+first[1]<sec[0]+sec[1];
});
Tree ffirst(positions.size()), fsec(positions.size());
// in this problem value (a, b) means y=a*x+b
/*
first and sec are values in positions.
Add the function multiplier*max(first-x, 0, x-sec) to tree.
(it's convex if multiplier>=0.)
*/
auto const addSlope=[&](Tree& tree, int first, int sec, int multiplier){
auto const ifirst=int(std::lower_bound(begin(positions), end(positions), first)-begin(positions));
auto const isec=int(std::lower_bound(begin(positions), end(positions), sec)-begin(positions));
assert(positions[ifirst]==first);
assert(positions[isec]==sec);
assert(first<=sec);
assert(tree.offset()==(int)positions.size());
tree.add(0, ifirst, {-1*multiplier, first*multiplier});
tree.add(isec, tree.offset(), {1*multiplier, -sec*multiplier});
// * Data could be std::pair<int, int64_t> * save implementation time!
};
for(auto [first, sec]: queries)
addSlope(fsec, first, sec, 1);
for(int slice=0, lastSum=0; slice<=(int)queries.size(); ++slice){
int curSum=slice==(int)queries.size() ? INT_MAX: queries[slice][0]+queries[slice][1];
if(curSum>lastSum){
// find minAdd in the current slice (first<=sec, lastSum<=first+sec<=curSum)
auto const ifirst=ffirst.minIndex();
auto const isec=fsec.minIndex();
auto const sum1=positions[ifirst]+positions[isec];
auto const searchFunction=[&](auto function, int left, int right){
// minAdd=min(minAdd, function(i)) for i in left..=right
// given that function is ternary (or something like that) on the segment
//
// complexity: log(value) calls to function. (which is actually pretty terrible?)
if(left>right) return; // just to be sure
int pos=left; auto value=function(pos);
auto const process=[&](int pos1){
auto const value1=function(pos1);
if(value1<value){
pos=pos1; value=value1;
}
};
for(int step=1<<30; step; step>>=1){
if((int64_t)pos-step>=left) process(pos-step);
if((int64_t)pos+step<=right) process(pos+step);
}
minAdd=std::min(minAdd, value);
assert(value==function(pos));
assert(left<=pos); assert(pos<=right);
assert(right-left<=500); // * only while debugging
for(int i=left; i<=right; ++i)
assert(function(i)>=value);
};
auto const searchSlope=[&](int sum){
assert(sum>=0);
assert(lastSum<=sum); assert(sum<=curSum);
// diff -> (sum-diff)/2, (sum+diff)/2
// diff=sum&1+2*x
// => ((sum-sum&1-2x)/2, (sum+sum&1+2x)/2)
// => ( (sum>>1)-x, ((sum+1)>>1)+x )
// obviously first<=sec
// need positions[0]<=first, sec<=positions.back()
// (to clarify: it's not "necessary", the result remains correct without that,
// but the current implementation of Tree::getAtValue can only handle those values)
searchFunction([&](int x){
auto const first=(sum>>1)-x, sec=((sum+1)>>1)+x;
assert(first<=sec);
assert(first+sec==sum);
return ffirst.getAtValue(first)+fsec.getAtValue(sec);
}, 0, std::min(positions.back()-((sum+1)>>1), (sum>>1)-positions[0]));
};
auto const searchC=[&]{
searchFunction([&](int value){
assert(lastSum<=value+value);
assert(value+value<=curSum);
return ffirst.getAtValue(value)+fsec.getAtValue(value);
}, std::max(positions[0], (lastSum+1)>>1), std::min(positions.back(), curSum>>1));
};
searchSlope(lastSum);
if(curSum!=INT_MAX)
searchSlope(curSum);
searchC();
if(lastSum<=sum1 and sum1<=curSum and ifirst<=isec)
minAdd=std::min(minAdd, ffirst.getAtIndex(ifirst)+fsec.getAtIndex(isec));
lastSum=curSum;
}else assert(curSum==lastSum);
if(slice!=(int)queries.size()){
// apply change from queries[slice]
auto const [first, sec]=queries[slice];
addSlope(fsec, first, sec, -1);
addSlope(ffirst, first, sec, 1);
}
}
std::cout<<result+minAdd*2<<'\n';
}
