C++

No description

fork
loading
Files
  • main.cpp
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using std::cin;
using std::ifstream;
using std::cout;
using std::vector;
using std::min;
using std::max;
using std::string;
using std::map;
using std::cerr;
using std::sort;
using std::__gcd;
using std::ios_base;

#define oo(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}
unsigned lcm(int a, int b) { return (a / __gcd(a, b) * b); }
#define fri(i,n) 			for(int i = 0 ; i < n;++i) 
#define jri(j,k,n) 		for(int j = k ; j >= n;j--) 
#define swapnumsxor 	a ^= b; b ^= a; a ^= b
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define inp(i) 				in >> i 
#define inp2(i,j) 		in >> i >> j  
#define inp3(i,j,k) 	in >> i >> j >> k
#define oup(i) 				cout << i << "\n"
#define oup2(i,j) 		cout << i << " "<<j<< "\n"
#define oup3(i,j,k) 	cout << i << " "<< j << " "<<k<< "\n"
#define MOD 1000000007
#define rmdup 				std::sort(str.begin(), str.end());str.erase(std::unique(str.begin(), str.end()), str.end());

typedef long long int lli;
typedef unsigned long long int ulli;
#define pb 		emplace_back
#define mp 		make_pair
#define MAXN 	1000000
#define vi vector<int>
#define vlli vector<lli>
#define vulli vector<ulli>
const int INF = 0x3f3f3f3f;
const long long arrsize = 1e5;
const long long segsize = 4*1e5;

vlli a(arrsize);
vlli seg(segsize);
template<typename T>
T getmid(T &lo , T &hi){
  return (lo + hi) >> 1;
}

template<typename T>
void buildtree( T idx ,T lo , T hi ){
  if(lo > hi) return;
  if( lo == hi ){
    seg[idx] = a[lo];
    return;
  }
  T mid = getmid(lo,hi);
  T l = idx << 1;
  buildtree(l, lo  , mid );
  buildtree(l+1, mid+1  , hi);
  seg[idx] = std::min( seg[l] ,seg[l+1]);
  return;
}

template<typename T>
T querymin( T idx ,T lo , T hi , T qs , T qe){
  if(lo > hi || qs > hi || qe < lo) return INT_MAX;
  if( lo >= qs && hi <= qe ){
    return seg[idx];
  }
  T mid = getmid(lo,hi);
  T l = querymin( idx << 1 , lo , mid , qs ,qe );
  T r = querymin( idx << 1|1 , mid+1 ,hi, qs ,qe );
  return min(l,r);
}

template<typename T>
T querymax( T idx ,T lo , T hi , T qs , T qe){
  if(lo > hi || qs > hi || qe < lo) return INT_MIN;
  if( lo >= qs && hi <= qe ){
    return seg[idx];
  }
  T mid = getmid(lo,hi);
  T l = querymax( idx << 1 , lo , mid , qs ,qe );
  T r = querymax( idx << 1|1 , mid+1 ,hi, qs ,qe );
  return max(l,r);
}

template<typename T>
void updatenode( T idx ,T lo , T hi , T i , T val){
  if(i > hi || i < lo) return;
  if( lo == hi ){
    seg[idx] = val;
    return ;
  }
  T mid = getmid(lo,hi);
  T l = idx << 1;
  updatenode( l , lo , mid , i,val );
  updatenode( l+1 , mid+1 ,hi, i,val );
  seg[idx] = min(seg[l] + seg[l+1]);
  return;
}

template<typename T>
void updaterange( T idx ,T lo , T hi , T rs , T re , T val){
  if(lo > hi || lo > re || hi < rs) return;
  if( lo >= rs && hi <= re ){
    seg[idx] = val;
    return ;
  }
  T mid = getmid(lo,hi);
  T l = idx << 1;
  updaterange( l , lo , mid , rs, re , val );
  updaterange( l+1 , mid+1 ,hi, rs,re,val );
  seg[idx] = min(seg[l] + seg[l+1]);
  return;
}


int main()
{ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
		ifstream in("inp.txt");
		
    return 0;
}