Hanasaki

1.9万

Horace_2
AcWing2AK
JiuCherish
im0use

Creme

the_xin
Tenshi

Bsqaq
unoff

XrkArul
warrior.
222222

Hanasaki
11天前

# 计算几何

Hanasaki
15天前
#include <cstdio>
#define getchar getchar_unlocked
#define putchar putchar_unlocked
//红黑树相关的宏定义函数,包括找兄弟,判断是左孩子右孩子,红黑节点
#define bro(x) (((x)->ftr->lc == (x)) ? ((x)->ftr->rc):((x)->ftr->lc))
#define islc(x) ((x)!=NULL && (x)->ftr->lc == (x))
#define isrc(x) ((x)!=NULL && (x)->ftr->rc == (x))
#define BLACK 0
#define RED 1
inline void write(int x) {
if (x < 0)
putchar('-'), x = -x;

if (x > 9)
write(x / 10);

putchar(x % 10 + 48);
}
int k = 0, f = 1;
char c = getchar();

while (c < '0' || c > '9') {
if (c == '-')
f = -1;

c = getchar();
}

while (c >= '0' && c <= '9') {
k = (k << 1) + (k << 3) + c - 48;
c = getchar();
}

return k * f;
}
template <typename T>
struct RedBlackTree {
/**红黑树节点**/
struct RBNode {
T val;//节点值
bool color;//true为红,false为黑
RBNode *ftr;
RBNode *lc, * rc;//父亲节点左孩子右孩子
int _size;//排名专用:记录以此点为根的树的规模

RBNode(T v = T(), bool RB = RED, RBNode *f = NULL,
RBNode *l = NULL, RBNode *r = NULL, int s = 1)
: val(v), color(RB), ftr(f), lc(l), rc(r), _size(s) {}

//删除节点专用后继
RBNode *single_succ() {
RBNode *ret = rc;

while (ret->lc) {
--(ret->_size);
ret = ret->lc;
}

return ret;
}
//直接前驱,从处注意可以是NULL
RBNode *pred() {
RBNode *ret = this;

if (!lc) {
while (ret->ftr && ret->ftr->lc == ret)
ret = ret->ftr;

ret = ret->ftr;
} else {
ret = ret->lc;

while (ret->rc)
ret = ret->rc;
}

return ret;
}
//直接后继
RBNode *succ() {
RBNode *ret = this;

if (!rc) {
while (ret->ftr && ret->ftr->rc == ret)
ret = ret->ftr;

ret = ret->ftr;
} else {
ret = ret->rc;

while (ret->lc)
ret = ret->lc;
}

return ret;
}
//维护域
void maintain() {
_size = 1;

if (lc)
_size += lc->_size;

if (rc)
_size += rc->_size;
}
};

/**外部不可见部分**/

RBNode *_root;//根节点
RBNode *_hot;//查找专用命中_hot

void init(T v) {
_root = new RBNode(v, BLACK, NULL, NULL, NULL, 1);
}

//统一重平衡代码,考虑3个节点4个子树
//分类讨论排序不在此处做,传入接口时是排好序的
void connect34(RBNode *nroot, RBNode *nlc, RBNode *nrc,
RBNode *ntree1, RBNode *ntree2, RBNode *ntree3, RBNode *ntree4) {
nlc->lc = ntree1;

if (ntree1)
ntree1->ftr = nlc;

nlc->rc = ntree2;

if (ntree2)
ntree2->ftr = nlc;

nrc->lc = ntree3;

if (ntree3)
ntree3->ftr = nrc;

nrc->rc = ntree4;

if (ntree4)
ntree4->ftr = nrc;

nroot->lc = nlc, nlc->ftr = nroot;
nroot->rc = nrc, nrc->ftr = nroot;
nlc->maintain(), nrc->maintain();
nroot->maintain();
}

//允许重复的查找,默认是找到同一个数的最后一个出现的位置
RBNode *find(T v, const int op) {
RBNode *ptn = _root;
_hot = NULL;

while (ptn) {
_hot = ptn;
ptn->_size += op;

if (ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}

return ptn;
}
//不允许重复的查找,只要找到对应值就收手
RBNode *rfind(T v, const int op) {
RBNode *ptn = _root;
_hot = NULL;

while (ptn && ptn->val != v) {
_hot = ptn;
ptn->_size += op;

if (ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}

return ptn;
}

//双红修正,采用迭代方式,迭代条件为RR-2上溢向上传2层
//判断双红的时候,自己得先是红的,然后判断父亲节点
void SolveDoubleRed(RBNode *nn) {
while ((!(nn->ftr)) || nn->ftr->color == RED) {
if (nn == _root) {
//根节点强制重染色为黑色,并且增加黑高度
_root->color = BLACK;
return;
}

RBNode *p = nn->ftr;

if (p->color == BLACK)
return;//case 1:没有双红,直接返回

RBNode *u = bro(p);
RBNode *g = p->ftr;

//case 2:RR-2
if (u != NULL && u->color == RED) {
g->color = RED;
p->color = u->color = BLACK;
nn = g;//下一次检查往上翻2层
}
//case 3:RR-1 直接返回
//此时就是要先根据情况调整父子节点位置,排好3+4结构,重染色
else {
if (islc(p)) {
if (islc(nn)) {//zig
p->ftr = g->ftr;

if (g == _root)
_root = p;
else if (g->ftr->lc == g)
g->ftr->lc = p;
else
g->ftr->rc = p;

connect34(p, nn, g, nn->lc, nn->rc, p->rc, u);
p->color = BLACK;
g->color = RED;
} else { //zag-zig
nn->ftr = g->ftr;

if (g == _root)
_root = nn;
else if (g->ftr->lc == g)
g->ftr->lc = nn;
else
g->ftr->rc = nn;

connect34(nn, p, g, p->lc, nn->lc, nn->rc, u);
nn->color = BLACK;
g->color = RED;
}
} else {
if (islc(nn)) {//zig-zag
nn->ftr = g->ftr;

if (g == _root)
_root = nn;
else if (g->ftr->lc == g)
g->ftr->lc = nn;
else
g->ftr->rc = nn;

connect34(nn, g, p, u, nn->lc, nn->rc, p->rc);
nn->color = BLACK;
g->color = RED;
} else { //zag
p->ftr = g->ftr;

if (g == _root)
_root = p;
else if (g->ftr->lc == g)
g->ftr->lc = p;
else
g->ftr->rc = p;

connect34(p, g, nn, u, p->lc, nn->lc, nn->rc);
p->color = BLACK;
g->color = RED;
}
}

return;
}
}
}

//双黑修正,采用迭代方式,迭代条件为BB-2B下溢向上传1层
//如果是根节点了,就可以直接停机了
void SolveDoubleBlack(RBNode *nn) {
while (nn != _root) {
RBNode *p = nn->ftr;
RBNode *b = bro(nn);

if (b->color == RED) { //Case 1:BB-3
b->color = BLACK;
p->color = RED;

if (_root == p)
_root = b;

if (p->ftr) {
if (p->ftr->lc == p)
p->ftr->lc = b;
else
p->ftr->rc = b;
}

b->ftr = p->ftr;

if (islc(nn))//zag
connect34(b, p, b->rc, nn, b->lc, b->rc->lc, b->rc->rc);
else//zig
connect34(b, b->lc, p, b->lc->lc, b->lc->rc, b->rc, nn);

b = bro(nn), p = nn->ftr;
//转换问题并往后接着推,维护的核心节点nn不变
}

if (b->lc && b->lc->color == RED) { //Case 2-1:BB-1
bool old_p_color = p->color;
p->color = BLACK;

if (p->lc == nn) {//zig-zag
if (p->ftr) {
if (p->ftr->lc == p)
p->ftr->lc = b->lc;
else
p->ftr->rc = b->lc;
}

b->lc->ftr = p->ftr;

if (_root == p)
_root = b->lc;

connect34(b->lc, p, b, nn, b->lc->lc, b->lc->rc, b->rc);
} else { //zig
b->lc->color = BLACK;

if (p->ftr) {
if (p->ftr->lc == p)
p->ftr->lc = b;
else
p->ftr->rc = b;
}

b->ftr = p->ftr;

if (_root == p)
_root = b;

connect34(b, b->lc, p, b->lc->lc, b->lc->rc, b->rc, nn);
}

p->ftr->color = old_p_color;
return;//BB-1直接返回
} else if (b->rc && b->rc->color == RED) { //Case 2-2:BB-1
bool old_p_color = p->color;
p->color = BLACK;

if (p->lc == nn) {//zag
b->rc->color = BLACK;

if (p->ftr) {
if (p->ftr->lc == p)
p->ftr->lc = b;
else
p->ftr->rc = b;
}

b->ftr = p->ftr;

if (_root == p)
_root = b;

connect34(b, p, b->rc, nn, b->lc, b->rc->lc, b->rc->rc);
} else { //zag-zig
if (p->ftr) {
if (p->ftr->lc == p)
p->ftr->lc = b->rc;
else
p->ftr->rc = b->rc;
}

b->rc->ftr = p->ftr;

if (_root == p)
_root = b->rc;

connect34(b->rc, b, p, b->lc, b->rc->lc, b->rc->rc, nn);
}

p->ftr->color = old_p_color;
return;//BB-1直接返回
}

if (p->color == RED) {//case 3:BB-2R
p->color = BLACK;
b->color = RED;
return;//BB-2R直接返回
} else { //case 4:BB-2B
b->color = RED;
nn = p;
//BB-2B下溢上传,继续迭代
}
}
}

RBNode *findKth(int Rank, RBNode *ptn) {
if (ptn->lc == NULL) {
if (Rank == 1)
return ptn;
else
return findKth(Rank - 1, ptn->rc);
} else {
if (ptn->lc->_size == Rank - 1)
return ptn;
else if (ptn->lc->_size >= Rank)
return findKth(Rank, ptn->lc);
else
return findKth(Rank - (ptn->lc->_size) - 1, ptn->rc);
}
}

int find_rank(T v, RBNode *ptn) {
if (!ptn)
return 1;
else if (ptn->val >= v)
return find_rank(v, ptn->lc);
else
return (1 + ((ptn->lc) ? (ptn->lc->_size) : 0) + find_rank(v, ptn->rc));
}

/**查看现象的debug接口**/

void previs(RBNode *ptn) {
printf("current node value is %d, color is %s, _size is %d\n", ptn->val, ptn->color ? "Red" : "Black",
ptn->_size);
printf("Lchild value is ");

if (ptn->lc)
printf("%d _size is %d\n", ptn->lc->val, ptn->lc->_size);
else
puts("NULL");

printf("Rchild value is ");

if (ptn->rc)
printf("%d _size is %d\n", ptn->rc->val, ptn->lc->_size);
else
puts("NULL");

if (ptn->lc)
previs(ptn->lc);

if (ptn->rc)
previs(ptn->rc);
}

void invis(RBNode *ptn) {
if (ptn->lc)
invis(ptn->lc);

printf("current node value is %d, color is %s, _size is %d\n", ptn->val, ptn->color ? "Red" : "Black",
ptn->_size);
printf("Lchild value is ");

if (ptn->lc)
printf("%d _size is %d\n", ptn->lc->val, ptn->lc->_size);
else
puts("NULL");

printf("Rchild value is ");

if (ptn->rc)
printf("%d _size is %d\n", ptn->rc->val, ptn->lc->_size);
else
puts("NULL");

if (ptn->rc)
invis(ptn->rc);
}

void postvis(RBNode *ptn) {
if (ptn->lc)
postvis(ptn->lc);

if (ptn->rc)
postvis(ptn->rc);

printf("current node value is %d, color is %s, _size is %d\n", ptn->val, ptn->color ? "Red" : "Black",
ptn->_size);
printf("Lchild value is ");

if (ptn->lc)
printf("%d _size is %d\n", ptn->lc->val, ptn->lc->_size);
else
puts("NULL");

printf("Rchild value is ");

if (ptn->rc)
printf("%d _size is %d\n", ptn->rc->val, ptn->lc->_size);
else
puts("NULL");
}

void checkconnect(RBNode *ptn) {
if (!ptn)
return;

if (ptn->lc && ptn->lc->ftr != ptn) {
printf("Oops! %d has a lc %d, but it failed to point its ftr!\n", ptn->val, ptn->lc->val);
}

if (ptn->rc && ptn->rc->ftr != ptn) {
printf("Oops! %d has a rc %d, but it failed to point its ftr!\n", ptn->val, ptn->rc->val);
}

int sss = ptn->_size;

if (ptn->lc)
sss -= ptn->lc->_size;

if (ptn->rc)
sss -= ptn->rc->_size;

if (sss - 1) {
printf("Fuck it! %d's size is %d, but the sum of its children's size is %d!\n", ptn->val, ptn->_size,
ptn->_size - sss);
}

checkconnect(ptn->lc);
checkconnect(ptn->rc);
}

void correctlyconnected() {
checkconnect(_root);
}

/**节点对应的迭代器**/
struct iterator {
//这个数据实际上也要private
RBNode *_real__node;

iterator &operator++() {
_real__node = _real__node->succ();
return *this;
}
iterator &operator--() {
_real__node = _real__node->pred();
return *this;
}
T operator*() {
return _real__node->val;
}

iterator(RBNode *node_nn = NULL) : _real__node(node_nn) {}
iterator(T const &val_vv) : _real__node(rfind(val_vv, 0)) {}
iterator(iterator const &iter) : _real__node(iter._real__node) {}

};

/**对外端口部分**/

RedBlackTree() : _root(NULL), _hot(NULL) {}

//插入 返回对应迭代器
iterator insert(T v) {
RBNode *ptn = find(v, 1);

if (_hot == NULL) {//仅有1个节点
init(v);
return iterator(_root);
}

ptn = new RBNode(v, RED, _hot, NULL, NULL, 1);

if (_hot->val <= v)
_hot->rc = ptn;
else
_hot->lc = ptn;

SolveDoubleRed(ptn);
return iterator(ptn);
}
//删除 返回成功或失败 本题中只可能是true
bool remove(T v) {
RBNode *ptn = rfind(v, -1);

if (!ptn)
return false;

RBNode *node_suc;

//单双分支情况处理
while (ptn->lc || ptn->rc) {
if (ptn->lc == NULL)
node_suc = ptn->rc;
else if (ptn->rc == NULL)
node_suc = ptn->lc;
else
node_suc = ptn->single_succ();

--(ptn->_size);
ptn->val = node_suc->val;
ptn = node_suc;
}

//当对应删去的节点为黑色,则需要双黑修正
if (ptn->color == BLACK) {
--(ptn->_size);
SolveDoubleBlack(ptn);
}

if (ptn == _root) {
_root = NULL;
delete ptn;
return true;
}

if (ptn->ftr->lc == ptn)
ptn->ftr->lc = NULL;
else
ptn->ftr->rc = NULL;

delete ptn;
return true;
}
//查排名
int get_rank(T v) {
return find_rank(v, _root);
}
int size() {
return _root->_size;
}
bool empty() {
return !_root;
}
iterator Kth(int Rank) {
return iterator(findKth(Rank, _root));
}
iterator lower_bound(T v) {
RBNode *ptn = _root;

while (ptn) {
_hot = ptn;

if (ptn->val < v)
ptn = ptn->rc;
else
ptn = ptn->lc;
}

if (_hot->val < v)
ptn = _hot;
else
ptn = _hot->pred();

return iterator(ptn);
}
iterator upper_bound(T v) {
RBNode *ptn = _root;

while (ptn) {
_hot = ptn;

if (ptn->val > v)
ptn = ptn->lc;
else
ptn = ptn->rc;
}

if (_hot->val > v)
ptn = _hot;
else
ptn = _hot->succ();

return iterator(ptn);
}

};
RedBlackTree<int> Tree;
int n;
int op, x, res;
RedBlackTree<int>::iterator it;
int main() {
Tree.insert(-2147483647), Tree.insert(2147483647);

while (n--) {

switch (op) {
case 0:
Tree.insert(x);
break;

case 1:
Tree.remove(x);
break;

case 2:
write(*(Tree.Kth(x + 1))), putchar('\n');
break;

case 3:
write(Tree.get_rank(x) - 2), putchar('\n');
break;

case 4:
res = *(Tree.lower_bound(x));
write(res == -2147483647 ? -1 : res), putchar('\n');
break;

case 5:
res = *(Tree.upper_bound(x));
write(res == 2147483647 ? -1 : res), putchar('\n');
break;

default:
puts("Invalid Instruction."), n++;
break;
}
}
}


Hanasaki
15天前
#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int inf = 1e12;

struct edge
{
int u, w, f, id;
};

vector<edge> g[200010];

struct EK
{
int s, t;
int MinCost, MaxFlow, len;
int dist[5005], h[5005], f[5005];
int pre[5005], e[5005];

void add(int x, int y, int z, int val)
{
int idx = (int)g[x].size(), idy = (int)g[y].size();
g[x].push_back({y, z, val, idy});
g[y].push_back({x, 0, -val, idx});
}

bool dijkstra()
{
for (int i = 0; i < 5005; i ++)
{
f[i] = 0;
dist[i] = inf;
}

priority_queue<pair<int, int>> que;
que.push({0, s});
dist[s] = 0;
while (!que.empty())
{
int x = que.top().second;
que.pop();
if (f[x])
continue;
f[x] = 1;
for (int i = (int)g[x].size() - 1; ~i; -- i)
{
int y = g[x][i].u, z = g[x][i].w, val = g[x][i].f;

if (z && dist[y] > dist[x] + val + h[x] - h[y])
{
dist[y] = dist[x] + val + h[x] - h[y];
pre[y] = x;
e[y] = i;
if (f[y] == 0)
que.push({-dist[y], y});
}
}
}
for (int i = 0; i <= len; i ++)
if (dist[i] < inf)
h[i] += dist[i];
memset(f, 0, sizeof f);
return dist[t] < inf;
}

int dfs(int x, int sum)
{
if (x == t || sum == 0)
return sum;
int sz = g[x].size(), res = 0;
f[x] = 1;
for (int i = 0; i < sz && sum != res; i ++)
{
int y = g[x][i].u, z = g[x][i].w, val = g[x][i].f, id = g[x][i].id;

if (z == 0 || f[y] || h[x] + val != h[y])
continue;
int now = dfs(y, min(sum - res, z));
g[x][i].w -= now;
g[y][id].w += now;
res += now;
MinCost += now * val;
}
f[x] = 0;
return res;
}

void dinic()
{
int now = 0;
while (dijkstra())
if (now = dfs(s, inf))
MaxFlow += now;
}

void ek()
{
int res = 0;
while (dijkstra())
{
int Min = inf;
for (int y = t, x = pre[t]; y != s; y = pre[y], x = pre[y])
Min = min(Min, g[x][e[y]].w);
for (int y = t, x = pre[t]; y != s; y = pre[y], x = pre[y])
g[x][e[y]].w -= Min, g[y][g[x][e[y]].id].w += Min;
MinCost += h[t] * Min;
MaxFlow += Min;
}
}
};

signed main()
{
int n, m; scanf("%lld %lld", &n, &m);

EK T;
T.s = 1;
T.t = n;
T.len = n;

for (int i = 0; i < m; i ++)
{
int x, y, z, val; scanf("%lld %lld %lld %lld", &x, &y, &z, &val);
}
T.dinic();
printf("%lld %lld\n", T.MaxFlow, T.MinCost);

return 0;
}


Hanasaki
16天前
// https://codeforces.com/contest/1677/problem/F
#include <bits/stdc++.h>
#define ll long long
const int mod=998244353,N=262145+10;

// just interpolation
namespace ns {
using namespace std;
int a[N],b[N],c[N],d[N],e[N],g[N],f2[N],rev[N],p[N],ans[N],qq[N],lim;
unsigned ll s[N];
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
inline void init(int mxn){
int l=0;
lim=1;
while(lim<mxn)
lim<<=1,l++;
for(int i=1;i<lim;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
int xx=qpow(3,mod>>l);
p[lim>>1]=1;
for(int i=lim/2+1;i<lim;i++)
p[i]=1ll*p[i-1]*xx%mod;
for(int i=lim/2-1;i>0;i--)
p[i]=p[i<<1];
}
inline int getL(int mxn){
return 1<<32-__builtin_clz(mxn);
}
inline void DFT(int *a,int len){
int x=__builtin_ctz(lim/len);
for(int i=0;i<len;i++)
s[i]=a[rev[i]>>x];
for(int i=1;i!=len;i<<=1){
int dg=i<<1;
for(int j=0;j!=len;j+=dg){
for(int k=0;k<i;k++){
int t1=s[i|j|k]*p[i|k]%mod;
s[i|j|k]=s[j|k]+mod-t1;
s[j|k]+=t1;
}
}
}
for(int i=0;i<len;i++)
a[i]=s[i]%mod;
}
inline void IDFT(int *a,int len){
reverse(a+1,a+len);
DFT(a,len);
for(int i=0;i<len;i++)
a[i]=1ll*a[i]*(mod-mod/len)%mod;
}
inline void Inv(int n,int *a,int *b){
qq[0]=qpow(a[0],mod-2);
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int dg=1;dg<n;dg<<=1){
for(int i=0;i<(dg<<1)&&i<n;i++)
c[i]=a[i];
for(int i=0;i<dg;i++)
d[i]=qq[i];
DFT(c,dg<<1),DFT(d,dg<<1);
for(int i=0;i<(dg<<1);i++)
c[i]=1ll*c[i]*d[i]%mod;
IDFT(c,dg<<1);
for(int i=0;i<dg;i++)
c[i]=0;
DFT(c,dg<<1);
for(int i=0;i<(dg<<1);i++)
c[i]=1ll*c[i]*d[i]%mod;
IDFT(c,dg<<1);
for(int i=dg;i<(dg<<1);i++)
qq[i]=1ll*c[i]*(mod-1)%mod;
}
for(int i=0;i<n;i++)
b[i]=qq[i];
}
inline void mul(int *a,int *b,int *s,int n,int m){
int len=getL(n+m-1);
static int c[N],d[N],e[N];
memset(c,0,len<<2);
memset(d,0,len<<2);
for(int i=0;i<n;i++)
c[i]=a[i];
for(int i=0;i<m;i++)
d[i]=b[i];
DFT(c,len),DFT(d,len);
for(int i=0;i<len;i++)
c[i]=1ll*c[i]*d[i]%mod;
IDFT(c,len);
for(int i=0;i<n+m-1;i++)
s[i]=c[i];
}
inline void mul2(int *a,int *b,int *s,int n,int m){
int len=getL(n);
static int c[N],d[N],e[N];
memset(c,0,len<<2);
memset(d,0,len<<2);
for(int i=0;i<n;i++)
c[i]=a[i];
for(int i=0;i<m;i++)
d[i]=b[m-i-1];
DFT(c,len),DFT(d,len);
for(int i=0;i<len;i++)
e[i]=1ll*c[i]*d[i]%mod;
IDFT(e,len);
for(int i=0;i<n-m+1;i++)
s[i]=e[m-1+i];
}
inline void Der(int *a,int *b,int n){
for(int i=1;i<n;i++)
b[i-1]=1ll*i*a[i]%mod;
b[n-1]=0;
}
int n,m,f[N],q[N],*t[N],*t2[N],buf[N<<5],*now=buf,sz[N],x[N],y[N];
inline void build(int l,int r,int rt){
t[rt]=now,now+=r-l+2,t2[rt]=now,now+=r-l+2;
if(l==r){
t[rt][0]=1;
t[rt][1]=x[l]?mod-x[l]:0;
return ;
}
int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
build(l,mid,ls),build(mid+1,r,rs);
mul(t[ls],t[rs],t[rt],mid-l+2,r-mid+1);
}
inline void solve(int l,int r,int rt,int *a){
if(l==r){
a[l]=t2[rt][0];
return ;
}
int mid=l+r>>1,ls=rt<<1,rs=rt<<1|1;
mul2(t2[rt],t[rs],t2[ls],r-l+1,r-mid+1);
solve(l,mid,ls,a);
mul2(t2[rt],t[ls],t2[rs],r-l+1,mid-l+2);
solve(mid+1,r,rs,a);
}
int tmp1[N],tmp2[N],tmp3[N],tmp4[N],answ[N],*stein[N];
inline void interpolation(int rt,int l,int r){
stein[rt]=new int[r-l+1];
if(l==r){
stein[rt][0]=answ[l];
return ;
}
int mid=l+r>>1;
interpolation(rt<<1,l,mid),interpolation(rt<<1|1,mid+1,r);
int len=getL(r-l+1);
for(int i=0;i<mid-l+1;i++)
tmp3[i]=stein[rt<<1][i];
for(int i=0;i<r-mid;i++)
tmp4[i]=stein[rt<<1|1][i];
mul(t[rt<<1|1],tmp3,tmp3,r-mid+1,mid-l+1);
mul(t[rt<<1],tmp4,tmp4,mid-l+1+1,r-mid);
for(int i=0;i<=r-l;i++)
stein[rt][i]=(tmp3[i]+tmp4[i])%mod;
}
inline void Interpolation(int *x,int *y,int *ans,int n){
int len=getL(n);
build(1,n,1);
for(int i=0;i<=n;i++)
tmp1[i]=t[1][i];
reverse(tmp1,tmp1+n+1);
Der(tmp1,tmp1,n+1);
Inv(n+1,t[1],tmp2);
mul2(tmp1,tmp2,t2[1],n*2-1,n);
solve(1,n,1,answ);
for(int i=1;i<=n;i++)
answ[i]=1ll*y[i]*qpow(answ[i],mod-2)%mod;
interpolation(1,1,n);
for(int i=0;i<n;i++)
ans[i]=stein[1][n-1-i];
}
}
using i64 = long long;

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
if (x < 0) {
x += P;
}
if (x >= P) {
x -= P;
}
return x;
}
template<class T>
T power(T a, int b) {
T res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
struct Z {
int x;
Z(int x = 0) : x(norm(x)) {}
int val() const {
return x;
}
Z operator-() const {
return Z(norm(P - x));
}
Z inv() const {
assert(x != 0);
return power(*this, P - 2);
}
Z &operator*=(const Z &rhs) {
x = i64(x) * rhs.x % P;
return *this;
}
Z &operator+=(const Z &rhs) {
x = norm(x + rhs.x);
return *this;
}
Z &operator-=(const Z &rhs) {
x = norm(x - rhs.x);
return *this;
}
Z &operator/=(const Z &rhs) {
return *this *= rhs.inv();
}
friend Z operator*(const Z &lhs, const Z &rhs) {
Z res = lhs;
res *= rhs;
return res;
}
friend Z operator+(const Z &lhs, const Z &rhs) {
Z res = lhs;
res += rhs;
return res;
}
friend Z operator-(const Z &lhs, const Z &rhs) {
Z res = lhs;
res -= rhs;
return res;
}
friend Z operator/(const Z &lhs, const Z &rhs) {
Z res = lhs;
res /= rhs;
return res;
}
};

std::vector<int> rev;
std::vector<Z> roots{0, 1};
void dft(std::vector<Z> &a) {
int n = a.size();

if (int(rev.size()) != n) {
int k = __builtin_ctz(n) - 1;
rev.resize(n);
for (int i = 0; i < n; i++) {
rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
}
}

for (int i = 0; i < n; i++) {
if (rev[i] < i) {
std::swap(a[i], a[rev[i]]);
}
}
if (int(roots.size()) < n) {
int k = __builtin_ctz(roots.size());
roots.resize(n);
while ((1 << k) < n) {
Z e = power(Z(3), (P - 1) >> (k + 1));
for (int i = 1 << (k - 1); i < (1 << k); i++) {
roots[2 * i] = roots[i];
roots[2 * i + 1] = roots[i] * e;
}
k++;
}
}
for (int k = 1; k < n; k *= 2) {
for (int i = 0; i < n; i += 2 * k) {
for (int j = 0; j < k; j++) {
Z u = a[i + j];
Z v = a[i + j + k] * roots[k + j];
a[i + j] = u + v;
a[i + j + k] = u - v;
}
}
}
}
void idft(std::vector<Z> &a) {
int n = a.size();
std::reverse(a.begin() + 1, a.end());
dft(a);
Z inv = (1 - P) / n;
for (int i = 0; i < n; i++) {
a[i] *= inv;
}
}
struct Poly {
std::vector<Z> a;
Poly() {}
Poly(const std::vector<Z> &a) : a(a) {}
Poly(const std::initializer_list<Z> &a) : a(a) {}
int size() const {
return a.size();
}
void resize(int n) {
a.resize(n);
}
Z operator[](int idx) const {
if (idx < size()) {
return a[idx];
} else {
return 0;
}
}
Z &operator[](int idx) {
return a[idx];
}
Poly mulxk(int k) const {
auto b = a;
b.insert(b.begin(), k, 0);
return Poly(b);
}
Poly modxk(int k) const {
k = std::min(k, size());
return Poly(std::vector<Z>(a.begin(), a.begin() + k));
}
Poly divxk(int k) const {
if (size() <= k) {
return Poly();
}
return Poly(std::vector<Z>(a.begin() + k, a.end()));
}
friend Poly operator+(const Poly &a, const Poly &b) {
std::vector<Z> res(std::max(a.size(), b.size()));
for (int i = 0; i < int(res.size()); i++) {
res[i] = a[i] + b[i];
}
return Poly(res);
}
friend Poly operator-(const Poly &a, const Poly &b) {
std::vector<Z> res(std::max(a.size(), b.size()));
for (int i = 0; i < int(res.size()); i++) {
res[i] = a[i] - b[i];
}
return Poly(res);
}
friend Poly operator*(Poly a, Poly b) {
if (a.size() == 0 || b.size() == 0) {
return Poly();
}
int sz = 1, tot = a.size() + b.size() - 1;
while (sz < tot) {
sz *= 2;
}
a.a.resize(sz);
b.a.resize(sz);
dft(a.a);
dft(b.a);
for (int i = 0; i < sz; ++i) {
a.a[i] = a[i] * b[i];
}
idft(a.a);
a.resize(tot);
return a;
}
friend Poly operator*(Z a, Poly b) {
for (int i = 0; i < int(b.size()); i++) {
b[i] *= a;
}
return b;
}
friend Poly operator*(Poly a, Z b) {
for (int i = 0; i < int(a.size()); i++) {
a[i] *= b;
}
return a;
}
Poly &operator+=(Poly b) {
return (*this) = (*this) + b;
}
Poly &operator-=(Poly b) {
return (*this) = (*this) - b;
}
Poly &operator*=(Poly b) {
return (*this) = (*this) * b;
}
Poly deriv() const {
if (a.empty()) {
return Poly();
}
std::vector<Z> res(size() - 1);
for (int i = 0; i < size() - 1; ++i) {
res[i] = (i + 1) * a[i + 1];
}
return Poly(res);
}
Poly integr() const {
std::vector<Z> res(size() + 1);
for (int i = 0; i < size(); ++i) {
res[i + 1] = a[i] / (i + 1);
}
return Poly(res);
}
Poly inv(int m) const {
Poly x{a[0].inv()};
int k = 1;
while (k < m) {
k *= 2;
x = (x * (Poly{2} - modxk(k) * x)).modxk(k);
}
return x.modxk(m);
}
Poly log(int m) const {
return (deriv() * inv(m)).integr().modxk(m);
}
Poly exp(int m) const {
Poly x{1};
int k = 1;
while (k < m) {
k *= 2;
x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k);
}
return x.modxk(m);
}
Poly pow(int k, int m) const {
int i = 0;
while (i < size() && a[i].val() == 0) {
i++;
}
if (i == size() || 1LL * i * k >= m) {
return Poly(std::vector<Z>(m));
}
Z v = a[i];
auto f = divxk(i) * v.inv();
return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);
}
Poly sqrt(int m) const {
Poly x{1};
int k = 1;
while (k < m) {
k *= 2;
x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((P + 1) / 2);
}
return x.modxk(m);
}
Poly mulT(Poly b) const {
if (b.size() == 0) {
return Poly();
}
int n = b.size();
std::reverse(b.a.begin(), b.a.end());
return ((*this) * b).divxk(n - 1);
}
std::vector<Z> eval(std::vector<Z> x) const {
if (size() == 0) {
return std::vector<Z>(x.size(), 0);
}
const int n = std::max(int(x.size()), size());
std::vector<Poly> q(4 * n);
std::vector<Z> ans(x.size());
x.resize(n);
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
q[p] = Poly{1, -x[l]};
} else {
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
q[p] = q[2 * p] * q[2 * p + 1];
}
};
build(1, 0, n);
std::function<void(int, int, int, const Poly &)> work = [&](int p, int l, int r, const Poly &num) {
if (r - l == 1) {
if (l < int(ans.size())) {
ans[l] = num[0];
}
} else {
int m = (l + r) / 2;
work(2 * p, l, m, num.mulT(q[2 * p + 1]).modxk(m - l));
work(2 * p + 1, m, r, num.mulT(q[2 * p]).modxk(r - m));
}
};
work(1, 0, n, mulT(q[1].inv(n)));
return ans;
}
};
int F[N];

int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

int n, k, p;
std::cin >> n >> k >> p;

std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}

std::vector<Z> g(k + 2);
for (int i = 1; i <= k + 1; i++) {
g[i] = g[i - 1] + power(Z(p), i) * power(Z(i), k);
}
std::vector<Z> fac(k + 2), invfac(k + 2);
fac[0] = 1;
for (int i = 1; i <= k + 1; i++) {
fac[i] = fac[i - 1] * i;
}
invfac[k + 1] = fac[k + 1].inv();
for (int i = k + 1; i; i--) {
invfac[i - 1] = invfac[i] * i;
}
for (int i = 0; i <= k + 1; i++) {
g[i] /= power(Z(p), i);
}

Z C = 0;
for (int i = 0; i <= k + 1; i++) {
C += fac[k + 1] * invfac[i] * invfac[k + 1 - i] * (i % 2 == 0 ? 1 : -1) * g[i];
}
C /= power(Z(1 - Z(p).inv()), k + 1);

for (int i = 0; i <= k + 1; i++) {
g[i] -= C / power(Z(p), i);
}

ns::init(2 * (k + 1));
for (int i = 0; i <= k; i++) {
ns::x[i + 1] = i;
ns::y[i + 1] = g[i].val();
}
ns::Interpolation(ns::x, ns::y, F, k + 1);

auto f = Poly(std::vector<Z>(F, F + k + 1)).eval(std::vector<Z>(a.begin(), a.end()));
for (int i = 0; i < n; i++) {
f[i] = f[i] * power(Z(p), a[i]) + C;
}

std::vector<Z> l(n), r(n);
for (int i = 0; i < n; i++) {
if (i == 0) {
l[i] = 1;
} else {
l[i] = l[i - 1] * (a[i - 1] + 1) + 1;
}
}
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) {
r[i] = 1;
} else {
r[i] = r[i + 1] * (a[i + 1] + 1) + 1;
}
}

Z ans = 0;
Z x = 0, y = 0;
for (int i = 0; i < n; i++) {
ans += f[i] * l[i] * r[i];
ans += (f[i] * x + a[i] * y) * r[i];
x *= a[i] + 1;
y *= a[i] + 1;
x += Z(a[i]) * l[i];
y += f[i] * l[i];
}
std::cout << ans.val() << "\n";

return 0;
}


Hanasaki
16天前
https://codeforces.com/contest/1684/problem/G
#include <bits/stdc++.h>

using i64 = long long;
struct Flow
{
static constexpr int INF = 1e9;
int n;
struct Edge
{
int to, cap;
Edge(int to, int cap) : to(to), cap(cap) {}
};
std::vector<Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
Flow(int n) : n(n), g(n) {}
bool bfs(int s, int t)
{
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty())
{
int u = que.front();
que.pop();
for (int i : g[u])
{
int v = e[i].to;
int c = e[i].cap;
if (c > 0 && h[v] == -1)
{
h[v] = h[u] + 1;
if (v == t)
return true;
que.push(v);
}
}
}
return false;
}
int dfs(int u, int t, int f)
{
if (u == t)
return f;
int r = f;
for (int &i = cur[u]; i < int(g[u].size()); ++i)
{
int j = g[u][i];
int v = e[j].to;
int c = e[j].cap;
if (c > 0 && h[v] == h[u] + 1)
{
int a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0)
return f;
}
}
return f - r;
}
void addEdge(int u, int v, int c)
{
g[u].push_back(e.size());
e.emplace_back(v, c);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
int maxFlow(int s, int t)
{
int ans = 0;
while (bfs(s, t))
{
cur.assign(n, 0);
ans += dfs(s, t, INF);
}
return ans;
}
};
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

int n, m;
std::cin >> n >> m;

std::vector<int> t(n);
for (int i = 0; i < n; i++)
{
std::cin >> t[i];
}

Flow flow(n + 2);
int source = n, sink = n + 1;

int count = 0;

for (int i = 0; i < n; i++)
{
if (3LL * t[i] > m)
{
count++;
}
else
{
}
}

for (int i = 0; i < n; i++)
{
if (3LL * t[i] > m)
{
for (int j = 0; j < n; j++)
{
if (3LL * t[j] <= m && t[i] % t[j] == 0 && 2LL * t[i] + t[j] <= m)
{
}
}
}
}

if (count != flow.maxFlow(source, sink))
{
std::cout << "-1\n";
return 0;
}

std::vector<bool> vis(n);
std::vector<std::array<int, 2>> ans;
for (int i = 2 * n; i < int(flow.e.size()); i += 2)
{
int u = flow.e[i + 1].to;
int v = flow.e[i].to;
int c = flow.e[i + 1].cap;

if (c > 0)
{
vis[u] = vis[v] = true;
ans.push_back({2 * t[u] + t[v], t[u] + t[v]});
}
}

for (int i = 0; i < n; i++)
{
if (!vis[i])
{
ans.push_back({3 * t[i], 2 * t[i]});
}
}

std::cout << ans.size() << "\n";
for (auto [x, y] : ans)
{
std::cout << x << " " << y << "\n";
}

return 0;
}


Hanasaki
16天前

Hanasaki
16天前
// https://codeforces.com/contest/1697/problem/F
#include <bits/stdc++.h>
using namespace std;
struct TwoSat
{
int n;
vector<vector<int>> e;
vector<bool> ans;
TwoSat(int n) : n(n), e(2 * n), ans(n) {}
void addClause(int u, bool f, int v, bool g)
{
e[2 * u + !f].push_back(2 * v + g);
e[2 * v + !g].push_back(2 * u + f);
}
bool satisfiable()
{
vector<int> id(2 * n, -1), dfn(2 * n, -1), low(2 * n, -1);
vector<int> stk;
int now = 0, cnt = 0;
function<void(int)> tarjan = [&](int u)
{
stk.push_back(u);
dfn[u] = low[u] = now++;
for (auto v : e[u])
{
if (dfn[v] == -1)
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (id[v] == -1)
{
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u])
{
int v;
do
{
v = stk.back();
stk.pop_back();
id[v] = cnt;
} while (v != u);
++cnt;
}
};
for (int i = 0; i < 2 * n; ++i)
if (dfn[i] == -1)
tarjan(i);
for (int i = 0; i < n; ++i)
{
if (id[2 * i] == id[2 * i + 1])
return false;
ans[i] = id[2 * i] > id[2 * i + 1];
}
return true;
}
vector<bool> answer() { return ans; }
};

void solve()
{
int n, m, k; cin >> n >> m >> k;

TwoSat ts(n * 2 * k);
for (int i = 0; i < n; i++)
{
int offset = 2 * k * i;
for (int j = 0; j < k - 1; j++)
{
ts.addClause(offset + j, false, offset + j + 1, true);
ts.addClause(offset + k + j, true, offset + k + j + 1, false);
ts.addClause(offset + j, true, offset + k + j + 1, true);
ts.addClause(offset + j, false, offset + k + j + 1, false);
}
ts.addClause(offset + k - 1, true, offset + k - 1, true);
ts.addClause(offset + k, true, offset + k, true);
}
for (int i = 0; i < n - 1; i++)
{
int offset1 = 2 * k * i;
int offset2 = 2 * k * (i + 1);
for (int j = 0; j < k; j++)
{
ts.addClause(offset1 + k + j, false, offset2 + k + j, true);
}
}

for (int i = 0; i < m; i++)
{
int t;
cin >> t;

if (t == 1)
{
int p, x;
cin >> p >> x;
x--;
p--;

int offset = 2 * k * p;

ts.addClause(offset + x, false, offset + k + x, false);
}
else if (t == 2)
{

int p, q, x;
cin >> p >> q >> x;
x -= 2;
p--;
q--;

int offset1 = 2 * k * p;
int offset2 = 2 * k * q;

if (x < k - 1)
{
ts.addClause(offset1 + x, true, offset1 + x, true);
ts.addClause(offset2 + x, true, offset2 + x, true);
}
for (int j = 0; j < x; j++)
{
if (j < k && x - 1 - j < k)
{
ts.addClause(offset1 + j, true, offset2 + x - 1 - j, true);
}
}
}
else
{

int p, q, x;
cin >> p >> q >> x;
x -= 2;
p--;
q--;

int offset1 = 2 * k * p;
int offset2 = 2 * k * q;

if (x > k - 1)
{
ts.addClause(offset1 + k + x - (k - 1), true, offset1 + k + x - (k - 1), true);
ts.addClause(offset2 + k + x - (k - 1), true, offset2 + k + x - (k - 1), true);
}
for (int j = 0; j < x + 1; j++)
{
if (j < k && x + 1 - j < k)
{
ts.addClause(offset1 + k + j, true, offset2 + k + x + 1 - j, true);
}
}
}
}

if (!ts.satisfiable())
{
cout << "-1\n";
return;
}

vector<int> a(n);

for (int i = 0; i < n; i++)
{
int offset = 2 * k * i;
for (int j = 0; j < k; j++)
{
if (ans[offset + j] && ans[offset + k + j])
{
a[i] = j;
}
}
cout << a[i] + 1 << " \n"[i == n - 1];
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

int T; cin >> T;
while (T --)
solve();

return 0;
}


Hanasaki
16天前
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

struct treap
{
#define ls t[p].lc
#define rs t[p].rc
struct tree
{
int val, cnt, siz, priority, lc, rc;
} t[maxn];
int root, tot, p1, p2, p3;
void push_up(int p)
{
t[p].siz = t[ls].siz + t[rs].siz + t[p].cnt;
}
int New(int val)
{
t[++tot] = tree{val, 1, 1, rand(), 0, 0};
}
void split(int p, int val, int &x, int &y)
{
if (!p)
{
x = 0;
y = 0;
return;
}

if (t[p].val <= val)
{
x = p;
split(t[p].rc, val, t[p].rc, y);
}
else
{
y = p;
split(t[p].lc, val, x, t[p].lc);
}

push_up(p);
}
int merge(int x, int y)
{
if (!x || !y)
return x + y;

if (t[x].priority > t[y].priority)
{
t[x].rc = merge(t[x].rc, y);
push_up(x);
return x;
}
else
{
t[y].lc = merge(x, t[y].lc);
push_up(y);
return y;
}
}
int find(int p, int val)
{
if (!p)
return 0;

if (t[p].val == val)
return p;

if (t[p].val < val)
return find(rs, val);
else
return find(ls, val);
}
void change(int p, int val, int k)
{
if (!p)
return;

if (t[p].val == val)
t[p].cnt += k;

if (t[p].val < val)
change(rs, val, k);
else if (t[p].val > val)
change(ls, val, k);

push_up(p);
}
void insert(int val)
{
int p = find(root, val);

if (p)
{
change(root, t[p].val, 1);
return;
}

split(root, val, p1, p2);
root = merge(merge(p1, New(val)), p2);
}
void erase(int val)
{
int p = find(root, val);

if (!p)
return;

if (t[p].cnt - 1 > 0)
{
change(root, t[p].val, -1);
return;
}

split(root, val - 1, p1, p2);
split(p2, val, p2, p3);
root = merge(p1, p3);
}
int point_rank(int val)
{
split(root, val - 1, p1, p2);
int ans = t[p1].siz + 1;
root = merge(p1, p2);
return ans;
}
int find_rank(int p, int rk)
{
if (!p)
return 0;

if (t[ls].siz >= rk)
return find_rank(ls, rk);

if (t[ls].siz + 1 <= rk && t[ls].siz + t[p].cnt >= rk)
return t[p].val;

return find_rank(rs, rk - t[ls].siz - t[p].cnt);
}
int get_pre(int val)
{
split(root, val - 1, p1, p2);
int ans = find_rank(p1, t[p1].siz);
root = merge(p1, p2);
return ans;
}
int get_after(int val)
{
split(root, val, p1, p2);
int ans = find_rank(p2, 1);
root = merge(p1, p2);
return ans;
}
} t;

int n, a1, a2;
int main()
{
scanf("%d", &n);

while (n--)
{
scanf("%d %d", &a1, &a2);

if (a1 == 1)
t.insert(a2);
else if (a1 == 2)
t.erase(a2);
else if (a1 == 3)
printf("%d\n", t.point_rank(a2));
else if (a1 == 4)
printf("%d\n", t.find_rank(t.root, a2));
else if (a1 == 5)
printf("%d\n", t.get_pre(a2));
else if (a1 == 6)
printf("%d\n", t.get_after(a2));
}
}


Hanasaki
16天前
// https://atcoder.jp/contests/abc254/tasks/abc254_f
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 2e5 + 5;
constexpr int mod = 998244353;

inline void solve()
{
int n, q; cin >> n >> q;

vector sta(20, vector<int>(n)), stb(sta);
vector<int> a(n), b(n);
for (int i = 0; i < n; i ++)
cin >> a[i];
for (int i = 0; i < n; i ++)
cin >> b[i];

for (int i = 0; i < n - 1; i ++)
{
sta[0][i] = abs(a[i + 1] - a[i]);
stb[0][i] = abs(b[i + 1] - b[i]);
}

for (int i = 1; (1LL << i) <= n; i ++) // 初始化
for (int j = 0; j + (1LL << i) <= n; j ++)
{
sta[i][j] = gcd(sta[i - 1][j], sta[i - 1][j + (1LL << (i - 1))]);
stb[i][j] = gcd(stb[i - 1][j], stb[i - 1][j + (1LL << (i - 1))]);
}

auto calc = [&](auto &st, int l, int r) // 区间查
{
if (l == r) return 0LL;
int x = 31 - (int)__builtin_clz(r - l);
return gcd(st[x][l], st[x][r - (1LL << x)]);
};

while (q --)
{
int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
x1 --;
x2 --;
y1 --;
y2 --;
int c = calc(sta, x1, x2);
int r = calc(stb, y1, y2);
cout << gcd(gcd(c, r), a[x1] + b[y1]) << '\n';
}
}

signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
/*
The details you should care:

*/


Hanasaki
16天前
#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);

string s; cin >> s;
int n = (int)s.size();
vector<int> sa(n), lc(n - 1), rk(n);
iota(sa.begin(), sa.end(), 0);
sort(sa.begin(), sa.end(), [&](const int &i, const int &j)
{
return s[i] < s[j];
});
rk[sa[0]] = 0;

for (int i = 1; i < n; i ++)
rk[sa[i]] = rk[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);

vector<int> tmp(n), cnt(n);
for (int k = 1; rk[sa[n - 1]] < n - 1; k *= 2)
{
tmp.clear();
for (int i = 0; i < k; i ++)
tmp.emplace_back(n - k + i);
for (int x : sa)
if (x >= k)
tmp.emplace_back(x - k);
fill(cnt.begin(), cnt.end(), 0);
for (int i = 0; i < n; i ++)
cnt[rk[i]] ++;
for (int i = 1; i < n; i ++)
cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; -- i)
sa[-- cnt[rk[tmp[i]]]] = tmp[i];
swap(rk, tmp);
rk[sa[0]] = 0;
for (int i = 1; i < n; i ++)
rk[sa[i]] = rk[sa[i - 1]] + (tmp[sa[i - 1]] < tmp[sa[i]] ||
sa[i - 1] + k == n ||
tmp[sa[i - 1] + k] < tmp[sa[i] + k]);
}
for (int i = 0, j = 0; i < n; i ++)
if (rk[i] == 0)
j = 0;
else
{
for (j -= (j > 0); i + j < n && sa[rk[i] - 1] + j < n && s[i + j] == s[sa[rk[i] - 1]] + j; j ++);
lc[rk[i] - 1] = j;
}
for (int i = 0; i < n; i ++)
cout << sa[i] << ' ';
cout << '\n';

return 0;
}