여름방학 합숙 훈련 - 데이터 구조
85400 단어 FSY 의 좋 은 문제 집합
#include
#define N 200000
using namespace std;
int read(){
int cnt = 0, f = 1; char ch = 0;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
return cnt * f;
}
int n, m, first[N], nxt[N<<1], to[N<<1], w[N<<1], tot;
void add(int x, int y, int z){
nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z;
}
typedef long long ll;
const int Base = 2, Mod = 1e9 + 7;
const int up = 150000;
ll Mul[N]; int st, ed, rt[N], idx;
struct President{
int ls, rs; ll sum;
}t[N * 100];
int modify(int last, int &x, int l, int r, int pos){
x = ++idx; t[x] = t[last];
if(l == r){ t[x].sum = t[last].sum ^ 1; return t[last].sum;}
int mid = (l+r) >> 1, res = 0;
if(pos <= mid){
res = modify(t[last].ls, t[x].ls, l, mid, pos);
if(res) res = modify(t[last].rs, t[x].rs, mid+1, r, pos);
}
else res = modify(t[last].rs, t[x].rs, mid+1, r, pos);
t[x].sum = (t[t[x].rs].sum * Mul[mid-l+1] % Mod + t[t[x].ls].sum) % Mod; return res;
}
bool Comp(int a, int b, int l, int r){
if(l == r) return t[a].sum > t[b].sum;
int mid = (l+r) >> 1;
if(t[t[a].rs].sum == t[t[b].rs].sum) return Comp(t[a].ls, t[b].ls, l, mid);
else return Comp(t[a].rs, t[b].rs, mid+1, r);
}
int from[N]; bool vis[N];
struct Node{
int x, rt;
Node(int _x = 0, int _rt = 0){ x = _x; rt = _rt;}
bool operator < (const Node &a) const{ return Comp(rt, a.rt, 0, up);}
}; priority_queue q;
void Print(int x, int dep){
if(x == st){ printf("%d
%d ", dep, x); return;}
Print(from[x], dep+1); printf("%d ", x);
}
void Dijsktra(){
q.push(Node(st, rt[st]));
while(!q.empty()){
int x = q.top().x, rot = q.top().rt; q.pop();
if(vis[x]) continue; vis[x] = true;
if(rt[x] != rot) continue;
if(x == ed){ printf("%lld
", t[rt[ed]].sum); Print(x, 1); return;}
for(int i = first[x]; i; i = nxt[i]){
int t = to[i]; int now = 0; modify(rt[x], now, 0, up, w[i]);
if(!rt[t] || Comp(rt[t], now, 0, up)){
from[t] = x;
rt[t] = now; q.push(Node(t, rt[t]));
}
}
} puts("-1");
}
int main(){
n = read(), m = read();
Mul[0] = 1;
for(int i = 1; i <= up; i++) Mul[i] = Mul[i-1] * Base % Mod;
for(int i = 1; i <= m; i++){
int x = read(), y = read(), z = read();
add(x, y, z); add(y, x, z);
} st = read(), ed = read();
Dijsktra(); return 0;
}
CF475F Meta - universe 의 폭력 적 인 방법 은 x x x 또는 y y 로 순 서 를 매 겨 x, y x, y x, y 를 쓸 고 쓸 면 양쪽 으로 자 르 는 것 이다. 그러나 가장 나 쁜 것 은 O (n 2) O (n ^ 2) O (n2) 의 폭력 적 인 방법 이다.작은 집합의 크기 를 고려 하면 하나의 큰 집합 을 하나의 작은 집합 과 하나의 큰 집합 으로 나 눌 수 있다. 약간의 계발 식 합병 은 작은 집합의 크기 로 하나의 큰 집합 으로 합 칠 수 있 기 때문에 복잡 도 는 O (n l o g n 2) O (nlogn ^ 2) O (nlogn 2) 를 계발 식 분열 이 라 고 해도 무방 하 다.
#include
using namespace std;
int read(){
int cnt = 0, f = 1; char ch = 0;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
return cnt * f;
}
struct Point{ int x, y; };
struct cmp1{ bool operator () (const Point &a, const Point &b){ return a.x < b.x || (a.x == b.x && a.y < b.y); }};
struct cmp2{ bool operator () (const Point &a, const Point &b){ return a.y < b.y || (a.y == b.y && a.x < b.x); }};
typedef set Sx;
typedef set Sy;
typedef Sx::iterator Itx;
typedef Sy::iterator Ity;
Sx sx; Sy sy;
int n, ans;
void Split(Sx &S1, Sy &S2){
Itx lx = S1.begin(), rx = --S1.end();
Ity ly = S2.begin(), ry = --S2.end();
int n = S1.size() >> 1;
for(int i = 1; i <= n; i++){
Itx tp = lx++;
if(tp->x + 1 < lx->x){
Sx S3; Sy S4; lx = ++tp;
for(tp = S1.begin(); tp != lx;){
Itx now = tp++;
S3.insert(*now);
S4.insert(*now);
S2.erase(*now);
S1.erase(now);
} Split(S1, S2); Split(S3, S4);
return;
}
tp = rx--;
if(rx->x + 1 < tp->x){
Sx S3; Sy S4; rx = --tp;
for(tp = --S1.end(); tp != rx;){
Itx now = tp--;
S3.insert(*now);
S4.insert(*now);
S2.erase(*now);
S1.erase(now);
} Split(S1, S2); Split(S3, S4);
return;
}
tp = ly++;
if(tp->y + 1 < ly->y){
Sx S3; Sy S4; ly = ++tp;
for(tp = S2.begin(); tp != ly;){
Ity now = tp++;
S3.insert(*now);
S4.insert(*now);
S2.erase(now);
S1.erase(*now);
} Split(S1, S2); Split(S3, S4);
return;
}
tp = ry--;
if(ry->y + 1 < tp->y){
Sx S3; Sy S4; ry = --tp;
for(tp = --S2.end(); tp != ry;){
Ity now = tp--;
S3.insert(*now);
S4.insert(*now);
S2.erase(now);
S1.erase(*now);
} Split(S1, S2); Split(S3, S4);
return;
}
} ++ans;
}
int main(){
n = read();
while(n--){
int x = read(), y = read(); Point now = (Point){x, y};
sx.insert(now); sy.insert(now);
} Split(sx, sy); cout << ans; return 0;
}
CF643G Choosing Ads 는 절대 다수 O (n) O (n) O (n) O (n) 방법 을 고려 하여 하나의 통 과 현재 의 수 를 유지 하 는 것 입 니 다한 구간 의 중 수 는 왼쪽 에 있 는 5 개 또는 오른쪽 에 있 는 5 개 입 니 다.
#include
#define N 150050
using namespace std;
int read(){
int cnt = 0, f = 1; char ch = 0;
while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
return cnt * f;
}
int n, m, p;
int a[N];
struct tree{
int num, tag, a[5], b[5];
tree operator + (const tree &A){
tree res = A; res.tag = 0;
for(int i = 0; i < num; i++){
bool flag = 0;
for(int j = 0; j < res.num; j++){
if(a[i] == res.a[j]){ flag = 1; res.b[j] += b[i]; break;}
}
if(flag) continue;
if(res.num < p){ res.a[res.num] = a[i]; res.b[res.num] = b[i]; ++res.num; continue;}
int k = 0;
for(int j = 1; j < res.num; j++) if(res.b[j] < res.b[k]) k = j;
if(b[i] < res.b[k]){ for(int j = 0; j < res.num; j++) res.b[j] -= b[i];}
else{
int tmp = res.b[k];
res.a[k] = a[i]; res.b[k] = b[i];
for(int j = 0; j < res.num; j++) res.b[j] -= tmp;
}
} return res;
}
} t[N<<2];
void build(int x, int l, int r){
if(l == r){ t[x].a[0] = a[l]; t[x].b[0] = t[x].num = 1; return;}
int mid = (l+r) >> 1; build(x<<1, l, mid); build(x<<1|1, mid+1, r);
t[x] = t[x<<1] + t[x<<1|1];
}
void pushnow(int x, int l, int r, int v){
t[x].num = 1; t[x].a[0] = v; t[x].b[0] = r - l + 1; t[x].tag = v;
}
void pushdown(int x, int l, int r){
if(t[x].tag){
int mid = (l+r) >> 1;
pushnow(x<<1, l, mid, t[x].tag);
pushnow(x<<1|1, mid+1, r, t[x].tag);
t[x].tag = 0;
}
}
void modify(int x, int l, int r, int L, int R, int v){
if(L<=l && r<=R){ pushnow(x, l, r, v); return;}
pushdown(x, l, r); int mid = (l+r) >> 1;
if(L<=mid) modify(x<<1, l, mid, L, R, v);
if(R>mid) modify(x<<1|1, mid+1, r, L, R, v);
t[x] = t[x<<1] + t[x<<1|1];
}
tree query(int x, int l, int r, int L, int R){
if(L<=l && r<=R) return t[x]; pushdown(x, l, r);
int mid = (l+r) >> 1;
if(L>mid) return query(x<<1|1, mid+1, r, L, R);
else if(R<=mid) return query(x<<1, l, mid, L, R);
else return query(x<<1, l, mid, L, R) + query(x<<1|1, mid+1, r, L, R);
}
int main(){
n = read(), m = read(), p = read(); p = 100 / p;
for(int i = 1; i <= n; i++) a[i] = read();
build(1, 1, n);
while(m--){
int op = read(), l = read(), r = read();
if(op == 1) modify(1, 1, n, l, r, read());
if(op == 2){
tree ans = query(1, 1, n, l, r);
cout << ans.num << " ";
for(int i = 0; i < ans.num; i++) cout << ans.a[i] << " ";
puts("");
}
} return 0;
}
CF 453 E Little Pony and Lord Tirek 은 말 마다 피 를 채 우 는 시간 t i t 를 계산 할 수 있 습 니 다.i ti 그리고 구간 [l, r] [l, r] [l, r] 사이 의 말 에 t i ti ti 정렬, 2 분 의 1 위치 로 앞 에 있 는 것 을 모두 피 로 채 웁 니 다. 뒤에 있 는 것 은 s u m (m i), s u m (r i) sum (m i), sum (r i) sum (mi) 을 처리 하지 못 했 습 니 다. sum (ri) 을 누 르 면 물 어 볼 수 있 습 니 다. t i ti ti 아래 에 주석 트 리 를 만 드 는 것 이 보기 좋 습 니 다. 또 어떤 조작 을 지원 해 야 하 는 지 보 겠 습 니 다. [l, r] [l, r] [l, r] 의 서로 다른 t t t t 구간 을 애 교 를 부리 고 모두 현재 t t t t 로 부 어 O D T ODT ODT 로 해결 합 니 다.
#include
#define N 100050
using namespace std;
typedef long long ll;
const int up = 100000;
int n, m, s[N], mx[N], rp[N];
int b[N], c[N]; ll sum[N];
#define pi pair
#define mp make_pair
pi operator + (const pi &a, const pi &b) { return mp(a.first + b.first, a.second + b.second);}
struct Presidentree{
bool op;
int rt[N], ls[N * 20], rs[N * 20], node;
ll val[N * 20], sum[N * 20];
void modify(int &x, int las, int l, int r, int pos, int p){
x = ++node; ls[x] = ls[las]; rs[x] = rs[las];
val[x] = val[las] + rp[p]; sum[x] = sum[las] + mx[p] - (op ? 0 : s[p]);
if(l == r) return; int mid = (l+r) >> 1;
if(pos <= mid) modify(ls[x], ls[las], l, mid, pos, p);
else modify(rs[x], rs[las], mid+1, r, pos, p);
}
pi query(int a, int b, int l, int r, int L, int R){
if(!a) return mp(0, 0);
if(L<=l && r<=R) return mp(val[a] - val[b], sum[a] - sum[b]);
int mid = (l + r) >> 1; pi ans = mp(0, 0);
if(L<=mid) ans = ans + query(ls[a], ls[b], l, mid, L, R);
if(R>mid) ans = ans + query(rs[a], rs[b], mid+1, r, L, R);
return ans;
}
}T[2];
struct Node{
int l, r, v;
Node(int _l = 0, int _r = 0, int _v = 0):l(_l),r(_r),v(_v){}
bool operator < (const Node &a) const{ return l < a.l;}
};
set S;
typedef set::iterator Int;
Int split(int p){
Int it = S.lower_bound(Node(p));
if(it != S.end() && it->l == p) return it;
it--;
int l = it->l, r = it->r, v = it->v;
S.erase(it);
S.insert(Node(l, p - 1, v));
it = S.lower_bound(Node(l, p - 1, v));
return S.insert(Node(p, r, v)).first;
}
ll ask(int t, int x, int y){
Int R = split(y + 1), L = split(x);
ll ans = sum[y] - sum[x - 1];
for(Int it = L; it != R; it++){
pi res;
if(it->v == 0) res = T[0].query(T[0].rt[it->r], T[0].rt[it->l - 1], 0, up + 1, min(up + 1, t - it->v + 1), up + 1);
else res = T[1].query(T[1].rt[it->r], T[1].rt[it->l - 1], 0, up + 1, min(up + 1, t - it->v + 1), up + 1);
ans += 1ll * res.first * (t - it->v) - res.second;
} S.erase(L, R); S.insert(Node(x, y, t));
return ans;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d%d%d", &s[i], &mx[i], &rp[i]);
sum[i] = sum[i-1] + (ll)mx[i];
if(rp[i] == 0) b[i] = c[i] = up + 1;
else{
b[i] = (mx[i] - s[i]) / rp[i] + ((mx[i] - s[i]) % rp[i] > 0);
c[i] = mx[i] / rp[i] + (mx[i] % rp[i] > 0);
}
} T[0].op = 0; T[1].op = 1;
for(int i = 1; i <= n; i++) T[0].modify(T[0].rt[i], T[0].rt[i-1], 0, up + 1, b[i], i);
for(int i = 1; i <= n; i++) T[1].modify(T[1].rt[i], T[1].rt[i-1], 0, up + 1, c[i], i);
S.insert(Node(1, n, 0)); S.insert(Node(n + 1, n + 1, 0));
scanf("%d", &m);
while(m--){
int t, l, r; scanf("%d%d%d", &t, &l, &r);
cout << ask(t, l, r) << '
';
} return 0;
}
굿 Subsegments 의 한 단락 은 좋 은 것 이 고, 그 다음 에 m a x (a i) − m i n (a i) = r − l max (a i) - min (a i) = r - l max (ai) − min (ai) = r − l 우 리 는 질문 을 오프라인 으로 하고, r r r r 순 으로, 선단트 리 로 동적 으로 m a x (a i) − m i n (a i) - (r − l) max (a i) - (a i) - min (a i) - (a i) - (r - l) max (ai) - min (ai) - min (ai) - min (ai) - (i) - (i) - min (ai) - min (ai) - min (ai) - (i) - (i) - l최소 값 및 최소 값 개수 고려 a i ai ai 의 공헌, 모든 위치 r r r 회 + 1 동시에 하나의 단조 로 운 스 택 을 유지, a i ai ai 는 m a x max max 의 구간 으로 a i - m a x a 를 통일 적 으로 추가 할 수 있 습 니 다.i - max ai − max, m i n min 과 같은 이치 로 r r 를 찾 았 습 니 다. 우 리 는 라인 트 리 에서 [l, r] [l, r] [l, r] 중 0 의 개수 등 을 조회 합 니 다. 여기 서 강제로 r 를 선택 한 것 을 찾 았 습 니 다. 분명히 틀 렸 습 니 다. 그래서 r 를 스 캔 한 후에 표 시 를 해서 현재 r 가 답 에 대한 기 여 를 내 려 놓 는 것 을 표시 합 니 다.
#include
#define N 200050
using namespace std;
typedef long long ll;
int n, m, a[N], mi[N], mx[N], top1, top2;
int Min[N<<2], sum[N<<2], ti[N<<2], tag[N<<2]; ll ans[N<<2], Ans[N];
struct qu{ int l, r, id;} q[N];
bool cmp(qu a, qu b){ return a.r < b.r;}
void pushmi(int x, int v){ Min[x] += v; tag[x] += v;}
void pushti(int x, int v){ ans[x] += 1ll * sum[x] * v; ti[x] += v;}
void pushdown(int x){
if(tag[x]){ pushmi(x<<1, tag[x]); pushmi(x<<1|1, tag[x]); tag[x] = 0;}
if(ti[x]){
if(Min[x<<1] == Min[x]) pushti(x<<1, ti[x]);
if(Min[x<<1|1] == Min[x]) pushti(x<<1|1, ti[x]);
ti[x] = 0;
}
}
void pushup(int x){
Min[x] = min(Min[x<<1], Min[x<<1|1]); sum[x] = 0;
if(Min[x] == Min[x<<1]) sum[x] += sum[x<<1];
if(Min[x] == Min[x<<1|1]) sum[x] += sum[x<<1|1];
ans[x] = ans[x<<1] + ans[x<<1|1];
}
void build(int x, int l, int r){
sum[x] = 1; Min[x] = l;
if(l == r) return; int mid = (l+r) >> 1;
build(x<<1, l, mid); build(x<<1|1, mid+1, r);
}
void modify(int x, int l, int r, int L, int R, int v){
if(L<=l && r<=R){ pushmi(x, v); return;}
pushdown(x); int mid = (l+r) >> 1;
if(L<=mid) modify(x<<1, l, mid, L, R, v);
if(R>mid) modify(x<<1|1, mid+1, r, L, R, v);
pushup(x);
}
ll query(int x, int l, int r, int L, int R){
if(L<=l && r<=R) return ans[x]; pushdown(x);
int mid = (l+r) >> 1; ll ret = 0;
if(L<=mid) ret += query(x<<1, l, mid, L, R);
if(R>mid) ret += query(x<<1|1, mid+1, r, L, R);
return ret;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
scanf("%d", &m);
for(int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
sort(q+1, q+m+1, cmp);
for(int i = 1, j = 1; i <= n; i++){
while(top1 && a[i] < a[mi[top1]]){
modify(1, 1, n, mi[top1-1] + 1, mi[top1], a[mi[top1]] - a[i]);
top1--;
} mi[++top1] = i;
while(top2 && a[i] > a[mx[top2]]){
modify(1, 1, n, mx[top2-1] + 1, mx[top2], a[i] - a[mx[top2]]);
top2--;
} mx[++top2] = i;
pushmi(1, -1);
pushti(1, 1);
while(j <= m && q[j].r == i) Ans[q[j].id] = query(1, 1, n, q[j].l, q[j].r), ++j;
}
for(int i = 1; i <= m; i++) cout << Ans[i] << "
";
return 0;
}
CF1083D The Fair Nut 's getting crazy 고려 매 거 진 구간 [b, c] [b, c] [b, c], 기 l i, r i li,r_i li, ri 는 색상 i 의 앞 뒤에 위치 가 나타 나 면 조건 을 만족 시 키 는 것 은 m a x (l i) < b, m i n (r i) > c max (l i) < b, min (r i) > c max (li) < b, min (ri) > c, 즉 a * 8712 ° [m a x (l i), b), d * 8712 ° [c, m i n (r i)) a \ in [max (l i), b), d \ in [c, min (r i))) a * 8712 °(b − m x) (m i − c) \ sum b (b - mx) (b − mx) \ \ sum b (b - mx) (mi - c) ∑ b (b − mx) (mi − mx) (mi − c) (b − m x) (m i − c) = ∑ b \8727m i - m x \8727m m i - b - b ∗ c + c ∗ m x m x \ sum b (b - mx) \ sum b * mix - mx - mx * b * mix - mx - mx * b * mix - mx - mx * c * c * c * c * c * c * c * c * c * c * c * c \8727m x x x - b * c + c * mx ∑ b (b − mx) (mi − c)= ∑ b ∗ mi − mx ∗ mi − b ∗ c + c ∗ mx 발견 각 i i i 에 대해 i ∗ m i * mi i ∗ mi, m i mi, m x mx mx, m i ∗ m x mi * mx mi ∗ mx 역시 단조 로 운 창고 로 mi 를 유지 하면 mx
#include
#define N 200050
using namespace std;
typedef long long ll;
const int Mod = 1e9+7;
int L[N], R[N], a[N], b[N], lst[N];
int mi[N], top1, mx[N], top2, n; ll ans;
void Add(ll &a, ll b){ a = a + b; if(a >= Mod) a -= Mod;}
ll add(ll a, ll b){ return (a + b) % Mod;}
ll mul(ll a, ll b){ return a * b % Mod; }
struct Node{
ll mx, mi, mxi, pmi, mit, mxt;
void merge(Node a, Node b){
mx = add(a.mx, b.mx), mi = add(a.mi, b.mi);
mxi = add(a.mxi, b.mxi); pmi = add(a.pmi, b.pmi);
}
}t[N<<2];
void pushup(int x){t[x].merge(t[x<<1], t[x<<1|1]);}
ll f(ll x){ return (x * (x + 1) / 2) % Mod;}
void pushmi(int x, int l, int r, int v){
Add(t[x].mit, v);
Add(t[x].mi, mul(v, r-l+1));
Add(t[x].mxi, mul(v, t[x].mx));
Add(t[x].pmi, mul(v, add(f(r), Mod-f(l-1))));
}
void pushmx(int x, int l, int r, int v){
Add(t[x].mxt, v);
Add(t[x].mx, mul(v, r-l+1));
Add(t[x].mxi, mul(v, t[x].mi));
}
void pushdown(int x, int l, int r){
int mid = (l+r) >> 1;
if(t[x].mit){ pushmi(x<<1, l, mid, t[x].mit); pushmi(x<<1|1, mid+1, r, t[x].mit); t[x].mit = 0;}
if(t[x].mxt){ pushmx(x<<1, l, mid, t[x].mxt); pushmx(x<<1|1, mid+1, r, t[x].mxt); t[x].mxt = 0;}
}
void modify(int x, int l, int r, int L, int R, int v, int op){
if(L<=l && r<=R){
if(!op) pushmi(x, l, r, v);
else pushmx(x, l, r, v);
return;
} pushdown(x, l, r); int mid = (l+r) >> 1;
if(L<=mid) modify(x<<1, l, mid, L, R, v, op);
if(R>mid) modify(x<<1|1, mid+1, r, L, R, v, op);
pushup(x);
}
Node query(int x, int l, int r, int L, int R){
if(L<=l && r<=R) return t[x]; pushdown(x, l, r);
int mid = (l+r) >> 1; Node ans = (Node){0, 0, 0, 0, 0, 0};
if(L<=mid) ans.merge(ans, query(x<<1, l, mid, L, R));
if(R>mid) ans.merge(ans, query(x<<1|1, mid+1, r, L, R));
return ans;
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
sort(b + 1, b + n + 1); int siz = unique(b+1, b+n+1) - (b+1);
for(int i = 1; i <= n; i++) a[i] = lower_bound(b+1, b+siz+1, a[i]) - b;
for(int i = 1; i <= n; i++){
L[i] = lst[a[i]] + 1; lst[a[i]] = i;
}
for(int i = 1; i <= siz; i++) lst[i] = n + 1;
for(int i = n; i >= 1; i--){
R[i] = lst[a[i]] - 1; lst[a[i]] = i;
}
for(int i = 1, pos = 1; i <= n; i++){
while(top1 && L[i] >= L[mx[top1]]){
modify(1, 1, n, mx[top1-1]+1, mx[top1], Mod-L[mx[top1]], 1);
top1--;
} modify(1, 1, n, mx[top1] + 1, i, L[i], 1); mx[++top1] = i;
while(top2 && R[i] <= R[mi[top2]]){
modify(1, 1, n, mi[top2-1]+1, mi[top2], Mod-R[mi[top2]], 0);
top2--;
} modify(1, 1, n, mi[top2] + 1, i, R[i], 0); mi[++top2] = i;
pos = max(pos, L[i]);
Node res = query(1, 1, n, pos, i);
ll tmp = Mod - mul(i, add(f(i), Mod - f(pos-1)));
Add(tmp, Mod - res.mxi);
Add(tmp, res.pmi);
Add(tmp, mul(i, res.mx));
Add(ans, tmp);
} cout << ans; return 0;
}
좋은 웹페이지 즐겨찾기
