## 【日常小测】回转寿司

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 400009;
const int M = 25009;
const int S = 1000;
const int B = N / S + 10;

int n, sn, m, arr[N];
priority_queue<int> val[B];
vector<int> opr[B];

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline void get_element(int w) {
if (opr[w].empty()) {
return;
}
priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end());
for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) {
if (arr[i] > heap.top()) {
heap.push(arr[i]);
arr[i] = heap.top();
heap.pop();
}
}
opr[w].clear();
}

inline int modify_element(int w, int s, int t, int v) {
get_element(w);
int tmp = -1;
for (int i = s; i <= t; i++) {
if (v < arr[i]) {
tmp = arr[i];
swap(v, arr[i]);
}
}
val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1));
return v;
}

inline int modify_block(int w, int v) {
val[w].push(v);
int ret = val[w].top();
val[w].pop();
if (v != ret) {
opr[w].push_back(v);
}
return ret;
}

inline int solve(int s, int t, int v) {
int ss = s / S, st = t / S;
v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v);
if (ss != st) {
for (int i = ss + 1; i < st; i++) {
v = modify_block(i, v);
}
v = modify_element(st, st * S, t, v);
}
return v;
}

int main() {
sn = n / S;
for (int i = 1; i <= n; i++) {
}
for (int i = 0; i <= sn; i++) {
val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1));
}
for (int tt = 1; tt <= m; tt++) {
if (s <= t) {
v = solve(s, t, v);
} else {
v = solve(s, n, v);
v = solve(1, t, v);
}
printf("%d\n", v);
}
return 0;
}


## 【日常小测】路径规划

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int M = N << 1;
const int INF = 1e9;

LL vout;

inline void Add_Edge(int u, int v, int c) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Divide_and_Conquer{
int rt,rt_sz,blk_sz,tot,sz[N],vis[N];
struct Data{
int mn,id; LL sum;
inline bool operator < (const Data &B) const {
return mn < B.mn;
}
}sta[N];
public:
void solve(int w, int blk) {
GetRoot(w, blk); vis[w=rt] = 1; tot = 0;
if (!vis[to[i]]) {
DFS(to[i], w, to[i], cost[i], cost[i]);
}
}
if (tot) update();
if (!vis[to[i]]) {
if (sz[to[i]] > sz[w]) sz[to[i]] = blk - sz[w];
solve(to[i], sz[to[i]]);
}
}
}
private:
inline void update() {
sort(sta+1, sta+1+tot);
LL mx1=0,mx2=0; int sur1=0,sur2=0;
for (int i=tot;i;i--) {
vout = max(vout, sta[i].mn * sta[i].sum);
if (sur1 && sur1 != sta[i].id) {
vout = max(vout, (mx1 + sta[i].sum) * sta[i].mn);
} else if (sur2 && sur2 != sta[i].id) {
vout = max(vout, (mx2 + sta[i].sum) * sta[i].mn);
}
if (sta[i].sum > mx1) {
if (sur1 == sta[i].id) {
mx1 = sta[i].sum;
} else {
mx2 = mx1; sur2 = sur1;
mx1 = sta[i].sum; sur1 = sta[i].id;
}
} else if (sta[i].sum > mx2) {
if (sur1 != sta[i].id) {
sur2 = sta[i].id;
mx2 = sta[i].sum;
}
}
}
}
inline void GetRoot(int w, int blk) {
rt_sz = INF; blk_sz = blk;
GetRoot1(w, w);
}
void GetRoot1(int w, int f) {
sz[w] = 1; int mx = 1;
if (to[i] != f && !vis[to[i]]) {
GetRoot1(to[i], w);
sz[w] += sz[to[i]];
mx = max(mx, sz[to[i]]);
}
}
mx = max(mx, blk_sz - sz[w]);
if (mx < rt_sz) rt_sz = mx, rt = w;
}
void DFS(int w, int f, int top, int mn, LL sum) {
bool tag = 1;
if (to[i] != f && !vis[to[i]]) {
DFS(to[i], w, top, mn>cost[i]?cost[i]:(tag=0,mn), cost[i] + sum);
}
}
if (!tag) return;
sta[++tot].mn = mn; sta[tot].id = top; sta[tot].sum = sum;
}
}DAC;

int main() {
for (int i=1,u,v;i<n;i++) {
}
DAC.solve(1, n);
printf("%lld\n",vout);
return 0;
}


#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300009;
const int M = N << 1;

int stp[N],p[N][2],fa[N][20],anc[N];
struct Edge{int u,v,c;}e[N];
LL vout,dep[N],MX[N];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

void DFS(int w, int f) {
fa[w][0] = f; stp[w] = stp[f] + 1;
if (to[i] != f) {
dep[to[i]] = dep[w] + cost[i];
DFS(to[i], w);
}
}
}

inline void AddEdge(int u, int v, int c, int id) {
static int E = 1; cost[E+1] = cost[E+2] = c;
e[id] = (Edge){u, v, c};
}

inline LL Dis(int u, int v) {
if (stp[v] < stp[u]) swap(u, v); int p1 = u, p2 = v;
for (int i=19;~i;i--) if (stp[fa[v][i]]>=stp[u]) v = fa[v][i];
if (u == v) return dep[p2] - dep[u];
for (int i=19;~i;i--) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];
return -(dep[fa[u][0]]<<1) + dep[p1] + dep[p2];
}

int find(int x) {return anc[x]==x?x:anc[x]=find(anc[x]);}

inline LL Merge(int u, int v) {
static LL ret, p1, p2; u = find(u); v = find(v);
if (MX[u] > MX[v]) ret = MX[u], p1 = p[u][0], p2 = p[u][1];
else ret = MX[v], p1 = p[v][0], p2 = p[v][1];
for (int i=0;i<=1;i++) {
for (int j=0;j<=1;j++) {
LL cur = Dis(p[u][i], p[v][j]);
if (cur > ret) {
ret = cur;
p1 = p[u][i];
p2 = p[v][j];
}
}
}
anc[u] = v; MX[v] = ret;
p[v][0] = p1; p[v][1] = p2;
return ret;
}

int main() {
for (int i=1,u,v;i<n;i++) {
}
DFS(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
sort(e+1, e+N, [](const Edge &A, const Edge &B){return A.c > B.c;});
for (int i=1;i<=n;i++) {
anc[i] = i;
p[i][0] = p[i][1] = i;
}
for (int i=1;i<n;i++) {
LL tmp = Merge(e[i].u, e[i].v);
vout = max(vout, tmp * e[i].c);
}
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 4326】[NOIP2015] 运输计划

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;
const int M = N << 1;

int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

namespace fastIO{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
bool IOerror=0;
inline char nc(){
static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
if (p1==pend){
if (pend==p1){IOerror=1;return -1;}
//{printf("IO error!\n");system("pause");for (;;);exit(0);}
}
return *p1++;
}
inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (sign)x=-x;
}
bool sign=0; char ch=nc(); x=0;
for (;blank(ch);ch=nc());
if (IOerror)return;
if (ch=='-')sign=1,ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
if (ch=='.'){
double tmp=1; ch=nc();
for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
}
if (sign)x=-x;
}
char ch=nc();
for (;blank(ch);ch=nc());
if (IOerror)return;
for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
*s=0;
}
for (c=nc();blank(c);c=nc());
if (IOerror){c=-1;return;}
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (bo)x=-x;
}
char ch;int bo=0;x=0;
for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
if (ch=='.'){
double tmp=1;
for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
}
if (bo)x=-x;
}
char ch=getchar();
for (;blank(ch);ch=getchar());
for (;!blank(ch);ch=getchar())*s++=ch;
*s=0;
}
#ifdef _WIN32
scanf("%I64d",&x);
#else
#ifdef __linux
scanf("%lld",&x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
//fwrite->write
struct Ostream_fwrite{
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void println(ll x){
static char s[25],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1); out('\n');
}
void print(double x,int y){
static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
if (x<-1e-12)out('-'),x=-x;x*=mul[y];
ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
}
void println(double x,int y){print(x,y);out('\n');}
void print(char *s){while (*s)out(*s++);}
void println(char *s){while (*s)out(*s++);out('\n');}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void println(int x){Ostream.println(x);}
inline void print(char x){Ostream.out(x);}
inline void println(char x){Ostream.out(x);Ostream.out('\n');}
inline void print(ll x){Ostream.print(x);}
inline void println(ll x){Ostream.println(x);}
inline void print(double x,int y){Ostream.print(x,y);}
inline void println(double x,int y){Ostream.println(x,y);}
inline void print(char *s){Ostream.print(s);}
inline void println(char *s){Ostream.println(s);}
inline void println(){Ostream.out('\n');}
inline void flush(){Ostream.flush();}
//puts->write
char Out[OUT_SIZE],*o=Out;
inline void print1(int x){
static char buf[15];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(int x){print1(x);*o++='\n';}
inline void print1(ll x){
static char buf[25];
char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
while(x)*p1++=x%10+'0',x/=10;
while(p1--!=buf)*o++=*p1;
}
inline void println1(ll x){print1(x);*o++='\n';}
inline void print1(char c){*o++=c;}
inline void println1(char c){*o++=c;*o++='\n';}
inline void print1(char *s){while (*s)*o++=*s++;}
inline void println1(char *s){print1(s);*o++='\n';}
inline void println1(){*o++='\n';}
inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
struct puts_write{
~puts_write(){flush1();}
}_puts;
inline void print2(int x){printf("%d",x);}
inline void println2(int x){printf("%d\n",x);}
inline void print2(char x){printf("%c",x);}
inline void println2(char x){printf("%c\n",x);}
inline void print2(ll x){
#ifdef _WIN32
printf("%I64d",x);
#else
#ifdef __linux
printf("%lld",x);
#else
puts("error:can't recognize the system!");
#endif
#endif
}
inline void println2(ll x){print2(x);printf("\n");}
inline void println2(){printf("\n");}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
fa[w][0] = f;
in[w] = ++div_cnt;
dep[w] = dep[f] + 1;
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = cost[i];
DFS(to[i], w);
}
}
out[w] = div_cnt;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (register int j=19;~j;j--) {
if (dep[fa[u][j]] >= dep[v]) {
u = fa[u][j];
}
}
if (u == v) return v;
for (register int j=19;~j;j--) {
if (fa[u][j] != fa[v][j]) {
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0];
}

inline bool judge(int lim) {
memset(delta,0,sizeof(delta));
int cnt = 0, MN = 0, MX = 0;
for (register int i=1;i<=m;i++) {
if (q[i].len > lim) {
cnt++;
MN = max(MN, q[i].len - lim);
delta[q[i].lca] -= 2;
delta[q[i].u] ++;
delta[q[i].v] ++;
}
}
for (register int i=n;i;i--)
delta[i] += delta[i+1];

for (register int i=1;i<=n;i++) {
if (delta[in[i]] - delta[out[i]+1] >= cnt) {
MX = max(sur[i], MX);
}
}
return MX >= MN;
}

int main(){
using namespace fastIO;
int l=0,r=0,mid,ret;
for (int i=1,u,v,w;i<n;i++) {
l = max(l, w);
}
DFS(1,1);
for (int j=1;j<=19;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca;i<=m;i++) {
q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
r = max(r, q[i].len);
q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
}

l = r - l; ret = r;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n",ret);
return 0;
}


—– UPD 2016.11.11 —–

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 300000+9;
const int M = N << 1;

int dep[N],fa[N][20],in[N],out[N],dis[N],n,m,div_cnt;
struct Query{int u,v,lca,len;}q[N];

static const int BUF_SIZE = 1000000;
static char buf[BUF_SIZE],*p1=0,*p2=0;
if (p1 == p2){
if (p2==p1) return -1;
} return *p1++;
}

return ret*f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void DFS(int w, int f) {
fa[w][0] = f;
in[w] = ++div_cnt;
dep[w] = dep[f] + 1;
if (to[i] != f) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = cost[i];
DFS(to[i], w);
}
}
out[w] = div_cnt;
}

inline int LCA(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (register int j=19;~j;j--) {
if (dep[fa[u][j]] >= dep[v]) {
u = fa[u][j];
}
}
if (u == v) return v;
for (register int j=19;~j;j--) {
if (fa[u][j] != fa[v][j]) {
u = fa[u][j];
v = fa[v][j];
}
}
return fa[u][0];
}

inline bool judge(int lim) {
memset(delta,0,sizeof(delta));
int cnt = 0, MN = 0, MX = 0;
for (register int i=1;i<=m;i++) {
if (q[i].len > lim) {
cnt++;
MN = max(MN, q[i].len - lim);
delta[q[i].lca] -= 2;
delta[q[i].u] ++;
delta[q[i].v] ++;
}
}
for (register int i=n;i;i--)
delta[i] += delta[i+1];

for (register int i=1;i<=n;i++) {
if (delta[in[i]] - delta[out[i]+1] >= cnt) {
MX = max(sur[i], MX);
}
}
return MX >= MN;
}

int main(){
int l=0,r=0,mid,ret;
for (int i=1,u,v,w;i<n;i++) {
l = max(l, w);
}
DFS(1,1);
for (int j=1;j<=19;j++) {
for (int i=1;i<=n;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
for (int i=1,u,v,lca;i<=m;i++) {
q[i].len = dis[u] + dis[v] - (dis[lca] << 1);
r = max(r, q[i].len);
q[i].u = in[u]; q[i].v= in[v]; q[i].lca = in[lca];
}

l = r - l; ret = r;
while (l <= r) {
mid = l + r >> 1;
if (judge(mid)) ret = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n",ret);
return 0;
}


## 【BZOJ 4523】[Cqoi2016] 路由表

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int M = 33000000;

int Stack[N];
bool ip[40];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Trie{
#define TRE Trie
int tot=1,ch[M][2],cnt,root=1,end[M];

inline void modify(int len){
int w = root;
for (int i=1;i<=len;i++) {
int c = ip[i];
if (ch[w]) w = ch[w];
else w = ch[w] = ++tot;
}
end[w] = ++cnt;
}

inline int query(int l, int r){
int top = 0, w = root, t = 1;
while (w) {
if (end[w]) {
while (top && Stack[top] > end[w]) top--;
Stack[++top] = end[w];
}
w = ch[w][ip[t]]; t++;
} t = 0;
for (int i=1;i<=top;i++)
if (Stack[i] > r) break;
else if (Stack[i] >= l) t++;
return t;
}
};

inline void Get_IP(){
memset(ip,0,sizeof(ip));
for (int j=1,sta=9;j<=4;j++,sta+=8) {
int TP = read(), i = 1;
while (TP) ip[sta-i] = TP & 1, TP >>= 1, i++;
}
}

int main(){
char c=getchar();
while (c != 'A' && c != 'Q') c=getchar();
if (c == 'A') {
Get_IP();