A 找矩阵
#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
I love Elaina;
const int N=3010;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int n,m,L[N][N],R[N][N],U[N][N],D[N][N],l1,r1,l2,r2,tl,tr;
char mp[N][N],tmp[N][N];
pair<int,int>pos;
void solve(){
# memset(L,0x3f,sizeof(L)),memset(R,-1,sizeof(R)),memset(U,0x3f,sizeof(U)),memset(D,-1,sizeof(D));
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(mp[i][j]=='S')pos=make_pair(i,j);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(mp[i][j]=='#')continue;
L[i][j]=min(j,L[i][j-1]);
}
for(int j=m;j;j--){
if(mp[i][j]=='#')continue;
R[i][j]=max(j,R[i][j+1]);
}
}
for(int j=1;j<=m;j++){
for(int i=1;i<=n;i++){
if(mp[i][j]=='#')continue;
U[i][j]=min(i,U[i-1][j]);
}
for(int i=n;i;i--){
if(mp[i][j]=='#')continue;
D[i][j]=max(i,D[i+1][j]);
}
}
for(int i=pos.first;i<=pos.first;i++){
for(int j=pos.first+1;j<=n;j++){
if(mp[j][pos.second]=='#')continue;
l1=L[i][pos.second],r1=R[i][pos.second],l2=L[j][pos.second],r2=R[j][pos.second],tl=tr=-1;
if(l1>=l2){
for(int k=l1;k<=pos.second;k++){
if(D[i][k]>=j){
tl=k;
break;
}
}
}
else{
for(int k=l2;k<=pos.second;k++){
if(U[j][k]<=i){
tl=k;
break;
}
}
}
if(r1<=r2){
for(int k=r1;k>=pos.second;k--){
if(D[i][k]>=j){
tr=k;
break;
}
}
}
else{
for(int k=r2;k>=pos.second;k--){
if(U[j][k]<=i){
tr=k;
break;
}
}
}
if(tl!=tr&&tl!=-1&&tr!=-1){
puts("Yes");
exit(0);
}
}
}
for(int i=1;i<pos.first;i++){
for(int j=pos.first;j<=pos.first;j++){
if(mp[i][pos.second]=='#')continue;
l1=L[i][pos.second],r1=R[i][pos.second],l2=L[j][pos.second],r2=R[j][pos.second],tl=tr=-1;
if(l1>=l2){
for(int k=l1;k<=pos.second;k++){
if(D[i][k]>=j){
tl=k;
break;
}
}
}
else{
for(int k=l2;k<=pos.second;k++){
if(U[j][k]<=i){
tl=k;
break;
}
}
}
if(r1<=r2){
for(int k=r1;k>=pos.second;k--){
if(D[i][k]>=j){
tr=k;
break;
}
}
}
else{
for(int k=r2;k>=pos.second;k--){
if(U[j][k]<=i){
tr=k;
break;
}
}
}
if(tl!=tr&&tl!=-1&&tr!=-1){
puts("Yes");
exit(0);
}
}
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
solve();
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)tmp[i][j]=mp[i][j];
swap(n,m);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)mp[i][j]=tmp[j][i];
solve();
puts("No");
return 0;
}
B 错峰旅行
#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
#define ll long long
I love Elaina;
const int N=5010;
const int M=1000010;
const ll mod=1e9+7;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int n,m,s,t,k,x,L[M],R[M],pos[M<<1],cur,p,qwq,d[M<<1];
ll ans=1;
int main(){
n=read(),m=read(),s=read(),t=read()+1;
for(int i=1;i<=m;i++)x=read(),L[i]=pos[2*i-1]=read(),R[i]=pos[2*i]=read()+1;
pos[2*m+1]=s,pos[2*m+2]=t;
sort(pos+1,pos+2*m+3);
k=unique(pos+1,pos+2*m+3)-pos-1;
s=lower_bound(pos+1,pos+k+1,s)-pos,t=lower_bound(pos+1,pos+k+1,t)-pos;
for(int i=1;i<=m;i++){
L[i]=lower_bound(pos+1,pos+k+1,L[i])-pos,R[i]=lower_bound(pos+1,pos+k+1,R[i])-pos;
d[L[i]]--,d[R[i]]++;
}
cur=n;
for(int i=1;i<t;i++){
cur+=d[i];
if(i>=s){
p=pos[i+1]-pos[i],qwq=cur;
while(p){
if(p&1)ans=1ll*ans*qwq%mod;
qwq=1ll*qwq*qwq%mod,p>>=1;
}
}
}
printf("%lld",ans);
return 0;
}
C 社交树
#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
#define ll long long
I love Elaina;
const int N=1e5+10;
const ll mod=1e8+7;
const int block=10000;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
ll n,m,A,op,x,y,head[N],cnt,siz[N],dfn[N],pos[N],p1[N],p2[N],idx,ans[N],dep[N];
struct edge{int to,nxt;}e[N<<1];
void addedge(int u,int v){e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;}
ll qp(int p){return 1ll*p2[p/block]*p1[p%block]%mod;}
void dfs(int u,int fa){
siz[u]=1,dfn[u]=++idx,pos[idx]=u,dep[u]=dep[fa]+1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
siz[u]+=siz[v];
}
}
namespace AyaseEli{
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
struct node{
int l,r;
ll val;
}tree[N<<2];
void pushdown(node *tree,int k){
if(tree[k].val){
tree[ls(k)].val=(tree[ls(k)].val+tree[k].val)%mod,tree[rs(k)].val=(tree[rs(k)].val+tree[k].val)%mod;
tree[k].val=0;
}
}
void build(node *tree,int k,int l,int r){
tree[k].l=l,tree[k].r=r;
if(l==r)return;
int mid=(l+r)/2;
build(tree,ls(k),l,mid),build(tree,rs(k),mid+1,r);
}
void change(node *tree,int k,int ql,int qr,ll v){
if(ql<=tree[k].l&&tree[k].r<=qr){
tree[k].val=(tree[k].val+v)%mod;
return;
}
pushdown(tree,k);
int mid=(tree[k].l+tree[k].r)/2;
if(ql<=mid)change(tree,ls(k),ql,qr,v);
if(mid<qr)change(tree,rs(k),ql,qr,v);
}
ll query(node *tree,int k,int q){
if(tree[k].l==tree[k].r)return tree[k].val;
pushdown(tree,k);
int mid=(tree[k].l+tree[k].r)/2;
if(q<=mid)return query(tree,ls(k),q);
else return query(tree,rs(k),q);
}
}
I love AyaseEli;
int main(){
n=read(),m=read(),A=(read()+mod)%mod;
p1[0]=p2[0]=1;
for(int i=1;i<=block;i++)p1[i]=1ll*p1[i-1]*A%mod;
for(int i=1;i<=block;i++)p2[i]=1ll*p2[i-1]*p1[block]%mod;
for(int i=2;i<=n;i++){
x=read();
addedge(x,i),addedge(i,x);
}
dfs(1,0),build(tree,1,1,n);
while(m--){
op=read();
if(op==1){
x=read(),y=(read()+mod-1)%(mod-1);
change(tree,1,dfn[x],dfn[x]+siz[x]-1,qp((y-dep[x]+mod-1)%(mod-1)));
}
if(op==2){
x=read();
printf("%lld\n",1ll*query(tree,1,dfn[x])*qp(dep[x])%mod);
}
}
return 0;
}