barrack
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
//#define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;
const int N = 5e5+5,M = 1e6+5,mod = 1e9+7;
int n,m,ans,top,s[N],ro[N],qp[N];
struct Edge
{
int u,v;
}e[M];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
while( ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}
namespace task1
{
inline int find(int x)
{
return ro[x]^x?ro[x]=find(ro[x]):x;
}
inline void merge(int x,int y)
{
int rx=find(x),ry=find(y); if(rx==ry) return ;
ro[rx]=ry;
}
inline int calc(int x)
{
fep(i,1,n) ro[i]=i;
fep(i,1,m) if(x^i) merge(e[i].u,e[i].v);
int res=0;
fep(i,1,top) res|=(find(s[i])!=find(s[1]));
return res;
}
inline void solve()
{
int res=0; if(!top) return ;
fep(i,1,m) res+=calc(i);
addmod(ans,qp[m-res]);
}
inline void dfs(int u)
{
if(u>n) return solve();
s[++top]=u; dfs(u+1);
--top; dfs(u+1);
}
inline void Solve()
{
dfs(1); printf("%d",ans);
}
}
namespace task4
{
inline void solve()
{
int ans=0;
fep(i,1,n)
{
addmod(ans,1ll*(i-1)*qp[m-1]%mod);
addmod(ans,qp[m]);
}
printf("%d",ans);
}
}
namespace task5
{
vector<int> G[N]; int ans=0,f[N][3];
inline void add(int u,int v)
{
G[u].emplace_back(v);
}
inline void dfs(int u,int fa)
{
f[u][0]=1;
for(auto v:G[u]) if(v^fa)
{
dfs(v,u);
addmod(f[u][2],1ll*Mod(f[u][1]+f[u][2])*Mod(f[v][1]+f[v][2])%mod);
addmod(f[u][1],1ll*f[u][0]*Mod(f[v][1]+f[v][2])%mod);
}
addmod(ans,1ll*Mod(f[u][1]+f[u][2])*qp[m-1]%mod);
addmod(ans,qp[m]);
addmod(f[u][1],1);
}
inline void solve()
{
fep(i,1,m) add(e[i].u,e[i].v),add(e[i].v,e[i].u);
dfs(1,0); printf("%d",ans);
}
}
signed main()
{
freopen("barrack.in","r",stdin);
// freopen("barrack2.in","r",stdin);
freopen("barrack.out","w",stdout);
n=read(),m=read(); qp[0]=1;
fep(i,1,m) qp[i]=2ll*qp[i-1]%mod;
bool flag=1;
fep(i,1,m)
{
int u=read(),v=read();
e[i]={u,v}; flag&=(abs(u-v)==1);
}
if(n<=16) task1::Solve();
else if(flag) task4::solve();
else if(n-1==m) task5::solve();
else puts("114514");
return 0;
}
match#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
#define int ull
#define ull unsigned long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;
const int N = 3e5+5;
ull n,mod=(1ll<<60),a[N],b[N];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
while( ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
namespace task1
{
ull f[3000+5][3000+5];
inline void solve()
{
fep(r,1,n)
{
ull mx1=0,mx2=0;
feb(l,r,1)
{
mx1=max(mx1,a[l]); mx2=max(mx2,b[l]);
f[l][r]=(f[l+1][r]+mx1*mx2%mod)%mod;
}
}
int Q=read();
while(Q--)
{
int l=read(),r=read(); ull ans=0;
fep(i,l,r) ans=(ans+f[l][i])%mod;
printf("%lld\n",(LL)ans);
}
}
}
namespace task2
{
int top=0,s[N],pre1[N],pre2[N];
inline ull mul(int x,int t)
{
ull ans=0;
while(t)
{
if(t&1) ans=(ans+x)%mod;
x=(x+x)%mod; t>>=1;
}
return ans;
}
inline void solve()
{
fep(i,1,n)
{
while(top&&a[s[top]]<a[i]) --top;
pre1[i]=s[top]; s[++top]=i;
}
top=0;
fep(i,1,n)
{
while(top&&b[s[top]]<b[i]) --top;
pre2[i]=s[top]; s[++top]=i;
}
int Q=read();
while(Q--)
{
int l=read(),r=read(); ull ans=0;
feb(i,r,l)
{
int p1=i,p2=i;
while(p1>=l&&p2>=l)
{
if(pre1[p1]<pre2[p2])
{
int L=max(l-1,pre2[p2]),R=min(p1,p2);
ans=(ans+mul(mul(R-L,a[p1]),b[p2]))%mod;
p2=pre2[p2];
}
else
{
int L=max(l-1,pre1[p1]),R=min(p1,p2);
ans=(ans+mul(mul(R-L,a[p1]),b[p2]))%mod;
p1=pre1[p1];
}
// cout<<i<<" "<<p1<<" "<<p2<<" "<<ans<<"\n";
}
}
printf("%lld\n",(LL)ans);
}
}
}
signed main()
{
freopen("match.in","r",stdin);
// freopen("match3.in","r",stdin);
freopen("match.out","w",stdout);
// if(system("fc /N /W match.out match3.ans")) puts("wa");
int _T=read(); n=read();
fep(i,1,n) a[i]=read();
fep(i,1,n) b[i]=read();
if(n<=3000) task1::solve();
else task2::solve();
return 0;
}
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
#define int long long
#define pr pair<int,int>
#define mpr make_pair
using namespace std;
const int N = 1e3+5,mod = 998244353;
int n,Vc,Vf,m,a[N][N],f[N][N],s[N],b[N][N],c[N][N],sum1[N],sum2[N];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
while( ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
inline int Mod(int x) {return x>=mod?x-mod:x;}
inline void addmod(int &x,int y) {x=Mod(x+y);}
signed main()
{
freopen("plant.in","r",stdin);
// freopen("plant3.in","r",stdin);
freopen("plant.out","w",stdout);
int _T=read(),Id=read();
while(_T--)
{
n=read(),m=read(),Vc=read(),Vf=read();
fep(i,1,n) fep(j,1,m) scanf("%1lld",&a[i][j]),b[i][j]=c[i][j]=0;
fep(i,1,n)
{
int top=0;
fep(j,1,m)
{
if(a[i][j]) while(top) b[i][s[top--]]=j;
else s[++top]=j;
}
while(top) b[i][s[top--]]=m+1;
}
fep(j,1,m)
{
int top=0;
fep(i,1,n)
{
if(a[i][j]) while(top) c[s[top--]][j]=i;
else s[++top]=i;
}
while(top) c[s[top--]][j]=n+1;
}
int ans1=0,ans2=0;
fep(i,1,m) sum1[i]=sum2[i]=0;
feb(i,n,1)
{
fep(j,1,m)//(x1,y0)
{
int res1=b[i][j]-j-1;
if(i+1>n||a[i+1][j]) continue;
// fep(k,i+2,n)
// {
// if(a[k][j]) break;
// int res2=b[k][j]-j-1;
// if(res2<=0) continue;
// int res3=c[k][j]-k-1;
// addmod(ans1,max(0ll,1ll*res1*res2%mod));
// addmod(ans2,max(0ll,1ll*res1*res2%mod*res3%mod));
// }
if(i+2>n||a[i+2][j]) sum1[j]=sum2[j]=0;
else
{
int res2=b[i+2][j]-j-1,res3=c[i+2][j]-(i+2)-1;
addmod(sum1[j],max(0ll,res2));
addmod(sum2[j],max(0ll,1ll*res2*res3%mod));
}
addmod(ans1,max(0ll,1ll*res1*sum1[j]));
addmod(ans2,max(0ll,1ll*res1*sum2[j]));
// cout<<i<<" "<<j<<" "<<ans1<<" "<<ans2<<"\n";
}
// cout<<i<<"\n";
// fep(j,1,m) cout<<sum1[j]<<" "; puts("");
}
printf("%lld %lld\n",1ll*ans1*Vc%mod,1ll*ans2*Vf%mod);
}
return 0;
}
///yl/hs/bx/yl
#include<bits/stdc++.h>
#define fep(i,l,r) for(int i=l;i<=r;++i)
#define feb(i,r,l) for(int i=r;i>=l;--i)
#define For(i,u) for(int i=head[u];i;i=e[i].nxt)
#define LL long long
//#define int long long
#define ld long double
#define pr pair<int,int>
#define mpr make_pair
using namespace std;
const int N = 300+5,M = 2e6+6;
int n,m,k,a[M],lst[N<<1],c[N<<1]; set<int> s;
struct Node
{
int opt,x,y;
}ans[M<<1];
inline int read()
{
int s=0,w=1; char ch=getchar();
while(!(ch>='0'&&ch<='9')) {if(ch=='-') w=-1; ch=getchar();}
while( ch>='0'&&ch<='9') {s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
return s*w;
}
inline void del(int x,int p)
{
// assert(lst[x]==p);
// cout<<x<<" "<<p<<"\n";
lst[x]=0;
c[p]=0;
s.insert(p);
}
inline void add(int x,int p)//color stack
{
lst[x]=p;
c[p]=x;
s.erase(p);
}
signed main()
{
freopen("meow.in","r",stdin);
// freopen("meow1.in","r",stdin);
freopen("meow.out","w",stdout);
int _T=read();
while(_T--)
{
n=read(),m=read(),k=read();
// cout<<n<<" "<<m<<" "<<k<<"\n";
fep(i,1,m) a[i]=read();
// fep(i,1,m) cout<<a[i]<<" "; puts("");
int cnt=0; s.clear();
fep(i,1,n-1) s.insert(i),s.insert(i+n);
fep(i,1,m)
{
// cout<<"lst:";
// fep(j,1,k) cout<<lst[j]<<" "; puts("");
if(lst[a[i]])
{
if(lst[a[i]]>n)//bottom
{
ans[++cnt]={1,n,0};
ans[++cnt]={2,lst[a[i]]-n,n};
del(a[i],lst[a[i]]);
}
else//top
{
ans[++cnt]={1,lst[a[i]]};
del(a[i],lst[a[i]]);
}
}
else
{
//c[x]:stack[x]'s color
//lst[x]:color[x] in stack
if(!s.empty())
{
int it=*s.begin(); // cout<<it<<"\n";
if(it>n)
{
int tmp=c[it-n];// cout<<c[it-n]<<"\n";
del(tmp,it-n);
add(tmp,it);
add(a[i],it-n);
}
else add(a[i],it);
ans[++cnt]={1,it>n?it-n:it,0};
}
else
{
int tmp=i+1,Lst=cnt+1; ans[++cnt]={1,0,0};
while(lst[a[tmp]]<n)// in top
{
if(lst[a[tmp]])
{
ans[++cnt]={1,lst[a[tmp]],0};
del(a[tmp],lst[a[tmp]]);
}
else
{
int it=*s.begin(); s.erase(it);
ans[++cnt]={1,it,0}; lst[a[tmp]]=it;
}
}
int S=lst[a[tmp]];
ans[Lst].x=S-n;
ans[++cnt]={1,n};
ans[++cnt]={2,S-n,n};
del(a[tmp],S); Lst=c[S-n];
del(Lst,S-n); add(Lst,S); add(a[i],S-n);
i=tmp;
}
}
}
printf("%d\n",cnt);
fep(i,1,cnt)
{
if(ans[i].opt==1) printf("%d %d\n",ans[i].opt,ans[i].x);
else printf("%d %d %d\n",ans[i].opt,ans[i].x,ans[i].y);
}
}
return 0;
}
标签:int,top,long,114,fep,ans,define
From: https://www.cnblogs.com/lasky/p/16927755.html