## T1

$mid\leq 1582$ 的，因为公元前 $4713$ 年是闰年，所以直接看看有多少年即可。对于 $mid>1582$ 的，先将 $1582$ 年以前的贡献加上，剩下的瞎搞搞就好了。

ll N;

inline bool check(ll year) {
if(year<1582) return (year%4==0);
else if(year==1582) return false;
else return (year%400==0||(year%4==0&&year%100!=0));
}
inline ll calc(ll year) {
if(year<=1582) {
year+=4712;
return 1ll*year*365+year/4+(year%4!=0);
} else {
ll tmp=1ll*6294*365+6294/4+(6294%4!=0)+355;
if(year==1583) return tmp;
year-=1584,tmp+=365;
return tmp+1ll*year*365+(year/4+(year%4!=0))-((year-17)/100)+((year-17)/400);
}
}

inline int lim(int u,bool nmsl) {
if(u==2) return nmsl?29:28;
if(u==1||u==3||u==5||u==7||u==8||u==10||u==12) return 31;
return 30;
}
inline void solve() {
IN(N);

ll l=-4712,r=1000000000,ans,mid;
while(l<=r) {
mid=l+r>>1;
(calc(mid+1)>N)?ans=mid,r=mid-1:l=mid+1;
}
N-=calc(ans);

int m=1,d=1;
while(N) {
if(d==lim(m,check(ans))) ++m,d=0;
if(ans==1582) {
if(m==10&&d==4) d=15;
else ++d;
} else ++d;
--N;
}
printf("%d %d ",d,m);
if(ans<=0) printf("%lld BC\n",-ans+1);
else printf("%lld\n",ans);
}


## T2

const int N=1e6+5;

int n,m,c,k,p[N],q[N],god[N];
ull a[N],all;

int main() {
IN(n),IN(m),IN(c),IN(k);
lep(i,1,n) IN(a[i]),all|=a[i];

lep(i,0,k-1) god[i]=true;
lep(i,1,m) IN(p[i]),IN(q[i]),god[p[i]]=false;

lep(i,1,m) if((all>>p[i])&1) god[p[i]]=true;

int tot=0;
lep(i,0,k-1) tot+=god[i];

if(n==0&&tot==64) printf("18446744073709551616\n");
else {
ull ans=0;
lep(i,0,tot-1) ans+=(1ull<<i);
printf("%llu\n",ans-n+1);
}
return 0;
}


## T3

const int N=1e5+5;
const int M=2e6+5;

struct Node {int T,P,V;} seq[N];
struct Edge {int nxt,to;} G[M];

inline void addedge(int u,int v) {
}

int vis[N],sum[N]; /*prod*/
int dfs(int u) {
if(vis[u]) return sum[u];
vis[u]=true;

int now=(seq[u].T==2)?seq[u].V:1;
return sum[u]=now;
}

int tag[N],ans[N];
queue <int> q;
inline void solve_topsort() {
lep(i,1,m) if(!du[i]) q.push(i);

while(!q.empty()) {
int u=q.front(); q.pop();
if(seq[u].T==1) pls(ans[seq[u].P],mul(tag[u],seq[u].V));

int now=tag[u];
int v=G[i].to;
pls(tag[v],now),now=mul(now,sum[v]);
if(--du[v],!du[v]) q.push(v);
}
}
}

int Q,f[N];
int main() {
IN(n);
lep(i,1,n) IN(a[i]);

IN(m);
lep(i,1,m) {
IN(seq[i].T);

if(seq[i].T==1) IN(seq[i].P),IN(seq[i].V);
if(seq[i].T==2) IN(seq[i].V);
if(seq[i].T==3) {
int C,g; IN(C);
}
}
lep(i,1,m) sum[i]=dfs(i);

IN(Q);
int now=1;
lep(i,1,Q) IN(f[i]);
rep(i,Q,1) pls(tag[f[i]],now),now=mul(now,sum[f[i]]);

solve_topsort();
lep(i,1,n) pls(ans[i],mul(a[i],now)),printf("%d ",ans[i]);
puts("");
return 0;
}


## T4

### Waring :: 这个做法假了

int dfs(int dep) {
if(dep==1) return 1;
int ans=dfs(dep-1);
return (die[top[dep]]>ans)?dep:ans;
}

inline void solve() {
lep(i,1,n) s.insert(mkp(b[i]=a[i],i));

rep(i,n,2) {
int y=(it=s.begin())->se,x=(it=s.end(),--it)->se;
s.erase(mkp(b[x],x)),s.erase(mkp(b[y],y)),s.insert(mkp(b[x]-=b[y],x));
top[i]=x,die[y]=i;
}
die[(it=s.begin())->se]=-1,s.clear();
printf("%d\n",dfs(n));
}


• $a_n$ 吃掉 $a_1$ 后不是最小蛇。

• $a_n$ 吃掉 $a_1$ 后成为最小蛇。

const int N=1e6+5;

int n,a[N],b[N],die[N],top[N];
deque <pii> q1,q2,tmp;

#define pp pop_back
#define po pop_front
#define pb push_back
#define pf push_front

int dfs(int dep) {
if(dep==1) return 1;
int ans=dfs(dep-1);
return (die[top[dep]]>ans)?dep:ans;
}

inline pii _min(deque <pii> &q) {return q.empty()?mkp(inf,0):q.back();}
inline pii _max(deque <pii> &q) {return q.empty()?mkp(-1,0):q.front();}

inline void solve() {
while(!q1.empty()) q1.pp();
while(!q2.empty()) q2.pp();
lep(i,1,n) q1.pf(mkp(b[i]=a[i],i)),die[i]=-1;

int x,y;
rep(i,n,2) {
(_max(q1)>_max(q2))?(x=q1.fro().se,q1.po()):(x=q2.fro().se,q2.po());
(_min(q1)<_min(q2))?(y=q1.bac().se,q1.pp()):(y=q2.bac().se,q2.pp());
q2.pb(mkp(b[x]-=b[y],x)),top[i]=x,die[y]=i;
}

printf("%d\n",dfs(n));
}


• 吃了之后，大蛇变成最小的蛇。
• 吃了之后，大蛇不变成最小的蛇。

const int N=1e6+5;
const int inf=1e9+7;

int n,ans,a[N],b[N];
deque <pii> q1,q2;

inline pii _min(deque <pii> &q) {return q.empty()?mkp(inf,0):q.back();}
inline pii _max(deque <pii> &q) {return q.empty()?mkp(-1,0):q.front();}

inline void solve() {
while(!q1.empty()) q1.pp();
while(!q2.empty()) q2.pp();
lep(i,1,n) q1.pf(mkp(b[i]=a[i],i));

int x,y,cur=-1; ans=0;
for(int i=n;i>=2;--i) {
(_max(q1)>_max(q2))?(x=q1.fro().se,q1.po()):(x=q2.fro().se,q2.po());
(_min(q1)<_min(q2))?(y=q1.bac().se,q1.pp()):(y=q2.bac().se,q2.pp());
pii now=mkp(b[x]-=b[y],x);

if(i>2&&now<min(_min(q1),_min(q2))) {(~cur)?(cur^=1):(cur=0);}
else {if(~cur) return ans+=cur,printf("%d\n",n-ans),void(); ++ans;}
q2.pb(now);
}
printf("%d\n",n-ans);
}


QAQ