吉首大学2019年程序设计竞赛
弱鸡的题解肯定有许多不足，如有错误或更好的方法，欢迎巨佬们指出，感谢 某些题可能会在今明两天写详细点QAQ（F题已加推理过程） A-SARS病毒 f[i][0]表示长度为i的合法字符串的数量， f[[i][1]表示仅A的个数为奇数的字符串数量 f[i][2]表示仅C的个数为奇数的字符串数量， f[[i][3]表示A, C个数都为奇数的字符串数量 很容易的可以推出状态转移方程组 ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧f[n][0]=2×f[n−1][0]+f[n−1][1]+f[n−1][2]f[n][1]=2×f[n−1][1]+f[n−1][0]+f[n−1][3]f[n][2]=2×f[n−1][2]+f[n−1][0]+f[n−1][3]f[n][3]=2×f[n−1][3]+f[n−1][1]+f[n−1][2] 可以从上面递推式中构建矩阵 ⎣⎢⎢⎡2110120110210112⎦⎥⎥⎤ 就可以用矩阵快速幂来写啦 不过我们通过观察发现 f[1][1]与 f[1][2]初始状态相同，而且以后迭代方程也相同，所以 f[n][1]=f[n][2] ∵f[n][0]+f[n][3]=f[n][1]+f[n][2] ∵f[n][0]+f[n][1]+f[n][2]+f[n][3]=4n ∴f[n][0]+f[n][3]=f[n][1]+f[n][2]=2×4n−1 ∴f[n−1][1]+f[n−1][2]=2×4n−2 ∴f[n][0]=2×f[n−1][0]+f[n−1][1]+f[n−1][2]=2×f[n−1][0]+2×4n−2 迭代后可以得到 f[n][0]=4n−1+2n−1 因为n比较大，记得欧拉降幂即可
其实还有更nb的解法得到最后表达式,用母函数 泰勒公式什么的,因为我不会，所以就不放上去了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1e5+5;
long long pow_mod(long long a,long long n,long long mod){
long long ret = 1;
long long temp = a%mod;
while(n){
if(n & 1)ret = ret*temp%mod; //mult_mod(ret,temp,mod);
temp = temp*temp%mod; //mult_mod(temp,temp,mod);
n >>= 1;
}
return ret;
}
char s[maxn];
int main(){
while(scanf("%s",s)!=EOF){
int len=strlen(s);
ll t=0;
for(int i=0;i<len;i++){
t=(t*10+(s[i]-'0'))%(mod-1);
}
ll ans;
ans=(pow_mod(4LL,t-1,mod)+pow_mod(2LL,t-1,mod))%mod;
printf("%lld\n",ans);
}
return 0;
}
B-干物妹小埋 树状数组求最长上升子序列：复制原数组，排序去重后，原数组从前往后扫，找到它在去重后数组的位置，树状数组维护的前i位最长上升子序列 这道题只不过加了权值而已，同理
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn = 200010;
int h[maxn];
long long tree[maxn];
vector<int> v;
ll get_sum(int x){
ll ans = 0;
while(x){
ans = max(ans, tree[x]);
x -= x&-x;
}
return ans;
}
void add(int x, ll val){
while(x < maxn){
tree[x] = max(tree[x], val);
x += x&-x;
}
}
int hash_id(int val){
return lower_bound(v.begin(), v.end(), val) - v.begin() + 1;
}
int main(){
int n;
scanf("%d", &n);
for(int i = 0 ; i < n ; i++){
scanf("%d", &h[i]);
v.push_back(h[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
ll ans = 0;
for(int i = 0, c ; i < n ; i++){
scanf("%d", &c);
int id = hash_id(h[i]);
ll temp = get_sum(id);
ans = max(ans, temp + c);
add(id, temp + c);
}
cout << ans << endl;
return 0;
}
C-手机锁屏 很抱歉标程出了问题（已修改） mp[i][j]表示i和j点之间是否有线,判断连线合法，之后再判断对称即可，但要注意有特殊情况，比如说序列是456的时候需要给mp[4][6]也加上一根线，比如说序列456328917，如果不加的话28连了线46没连会判不对称。
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
namespace fast{inline char nc(){static char buf[100000],*L=buf,*R=buf;return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;}template<class orz> inline void qread(orz &x){x=0;char ch=nc();bool f=0;while(ch<'0'||ch>'9')(ch=='-')&&(f=1),ch=nc();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=nc();f&&(x=-x);}}using namespace fast;
template<class orz>inline void read(orz &x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9')(ch=='-')&&(f=1),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();f&&(x=-x);}
template<class orz>inline void out(orz x){(x<0)&&(putchar('-'),x=-x);if(x>9)out(x/10);putchar(x%10+'0');}
#define inf 0x3f3f3f3f
#define ***(x) out(x),putchar(10)
#define space(x) out(x),putchar(32)
#define mem(a,b) memset(a,b,sizeof(a))
///******************************head*************************************///
const double eps=1e-9;const ll mod=1e9+7;//998244353;
const int M=1e5+7,N=2e5+7;
int T,m,n;
int a[9];
bool mp[10][10],used[10];
bool link(int x,int y)
{
if(used[y]){return false;}
used[x]=used[y]=mp[x][y]=mp[y][x]=true;
if((x==1&&y==3)||(x==3&&y==1)) used[2]=mp[x][2]=mp[2][x]=mp[y][2]=mp[2][y]=true;
if((x==7&&y==9)||(x==9&&y==7)) used[8]=mp[x][8]=mp[8][x]=mp[y][8]=mp[8][y]=true;
if((x==7&&y==1)||(x==1&&y==7)) used[4]=mp[x][4]=mp[4][x]=mp[y][4]=mp[4][y]=true;
if((x==3&&y==9)||(x==9&&y==3)) used[6]=mp[x][6]=mp[6][x]=mp[y][6]=mp[6][y]=true;
if((x==1&&y==9)||(x==9&&y==1)) used[5]=mp[x][5]=mp[5][x]=mp[y][5]=mp[5][y]=true;
if((x==3&&y==7)||(x==7&&y==3)) used[5]=mp[x][5]=mp[5][x]=mp[y][5]=mp[5][y]=true;
if((x==4&&y==6)||(x==6&&y==4)) used[5]=mp[x][5]=mp[5][x]=mp[y][5]=mp[5][y]=true;
if((x==2&&y==8)||(x==8&&y==2)) used[5]=mp[x][5]=mp[5][x]=mp[y][5]=mp[5][y]=true;
return true;
}
int f(int x)
{
if((x-1)%3==0) return x+2;
if((x-1)%3==2) return x-2;
return x;
}
int g(int x)
{
if(x>=1&&x<=3) return x+6;
if(x>=7&&x<=9) return x-6;
return x;
}
int h(int x)
{
if(x==2) return 4;if(x==4) return 2;
if(x==3) return 7;if(x==7) return 3;
if(x==6) return 8;if(x==8) return 6;
return x;
}
int w(int x)
{
if(x==1) return 9;if(x==9) return 1;
if(x==2) return 6;if(x==6) return 2;
if(x==4) return 8;if(x==8) return 4;
return x;
}
bool judge()
{
bool ff,gg,hh,ww;
ff=gg=hh=ww=true;
for(int i=1;i<=9;i++)
for(int j=i+1;j<=9;j++){
if(mp[i][j]!=mp[f(i)][f(j)]) ff=false;
if(mp[i][j]!=mp[g(i)][g(j)]) gg=false;
if(mp[i][j]!=mp[h(i)][h(j)]) hh=false;
if(mp[i][j]!=mp[w(i)][w(j)]) ww=false;
}
return ff||gg||hh||ww;
}
int main()
{
//ifstream ifile("in.txt");
//ofstream ofile("out.txt");
for(int i=0;i<9;i++) a[i]=i+1;
int cnt=0;
do{
mem(mp,false);
mem(used,false);
bool ok=true;
for(int i=0;i<8;i++){
if(!link(a[i],a[i+1])){
ok=false;
break;
}
}
for(int i=2;i<9;i++){
if(a[i-2]==1&&a[i-1]==2&&a[i]==3) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==3&&a[i-1]==2&&a[i]==1) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==4&&a[i-1]==5&&a[i]==6) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==6&&a[i-1]==5&&a[i]==4) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==7&&a[i-1]==8&&a[i]==9) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==9&&a[i-1]==8&&a[i]==7) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==1&&a[i-1]==4&&a[i]==7) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==7&&a[i-1]==4&&a[i]==1) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==2&&a[i-1]==5&&a[i]==8) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==8&&a[i-1]==5&&a[i]==2) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==3&&a[i-1]==6&&a[i]==9) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==9&&a[i-1]==6&&a[i]==3) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==1&&a[i-1]==5&&a[i]==9) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==9&&a[i-1]==5&&a[i]==1) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==3&&a[i-1]==5&&a[i]==7) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
if(a[i-2]==7&&a[i-1]==5&&a[i]==3) mp[a[i-2]][a[i]]=mp[a[i]][a[i-2]]=true;
}
if(ok&&judge()){
for(int i=0;i<9;i++) putchar('0'+a[i]);putchar(10),cnt++;
}
}while(next_permutation(a,a+9));
//***(cnt);
return 0;
}
D-数列求和(嘤雄难度) 换元，迭代，错位相减，累加可以求得 Ai=i∗i+i（打表找规律） 我们可以考虑先求出所有与 m不互质的和，再相减即为所求 预处理m的质因子，个数不多 与m不互质的肯定与m有共同的质因子，枚举出所有质因子的组合 假设 k=某些质因子相乘，n中与m有k这个公约数的个数就有 kn再用求和公式+容斥就可以得到对答案的贡献
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=3e5+5;
const int MAXN=10005;
int prime[MAXN];
bool vis[MAXN];
void getPrime(int n){
for(int i=2;i<=n;i++){
if(!vis[i]) prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;//关键
}
}
}
int p[100],c[100];int tol;
// p素因子 c 次数
void divide(ll n){
tol=0;
for(int i=1;i<=prime[0]&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
p[++tol]=prime[i],c[tol]=0;
while(n%prime[i]==0) n/=prime[i],c[tol]++;
}
}
if(n>1){
p[++tol]=n,c[tol]=1;
}
}
long long pow_mod(long long a,long long n,long long mod){
long long ret = 1;
long long temp = a%mod;
while(n){
if(n & 1)ret = ret*temp%mod; //mult_mod(ret,temp,mod);
temp = temp*temp%mod; //mult_mod(temp,temp,mod);
n >>= 1;
}
return ret;
}
ll n,m;
ll inv6,inv2;
int main(){
inv2=500000004;
inv6=166666668;
getPrime(MAXN-1);
while(scanf("%lld%lld",&n,&m)!=EOF){
divide(m);
ll ans=0;
for(int i=1;i<(1<<tol);i++){
ll sum=0,c=1,k=1;
for(int j=0;j<tol;j++){
if((1<<j)&i){
sum++;k*=p[j+1];
}
}
if(sum&1){
c=n/k;
// printf("%d %d",c,p[i]) ;
ans=(ans+k*k%mod*c%mod*(c+1)%mod*(2*c+1)%mod*inv6%mod+k*c%mod*(c+1)%mod*inv2%mod)%mod;
}
else{
c=n/k;
// printf(" %d\n",c) ;
ans=(ans-k*k%mod*c%mod*(c+1)%mod*(2*c+1)%mod*inv6%mod-k*c%mod*(c+1)%mod*inv2%mod+mod)%mod;
}
}
ans=(n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod+n*(n+1)%mod*inv2%mod-ans+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
E-多喝嘤料 模拟即可
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9;
const int maxn=1e3+5;
int main(){
int t;
scanf("%d",&t);
while(t--){
ll n,ans=0;
scanf("%lld",&n);
ans+=n;
ll p=n,g=n;
while(p>=3||g>=4){
int now=p/3+g/4;
p%=3;g%=4;
p+=now;g+=now;
ans+=now;
}
printf("%lld\n",ans);
}
return 0;
}
F-天花乱坠 上图以正六边形位例，帮助理解，设最开始的每条边长位 len,图中的S角为 θ,正 n边行,那么边长和就是 n∗len+n∗2len∗cos(θ)∗2+n∗len∗cos2(θ)+... 求和后得到 n∗len∗(1−cos(θ)1−cosx(θ)) 当 x→∞时 cosx(θ)→0 综上，我们只需考虑如何求 θ; 我们知道内角和公式是 (n−2)∗π 就很容易得到 θ=2(π−n(n−2)∗π)=nπ 问题得解
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9;
const int maxn=1e3+5;
int main(){
int n;
double len=100;
while(scanf("%d",&n)!=EOF){
double s=PI/n;
double ans=n*len;
ans=ans/(1-cos(s));
printf("%.2f\n",ans);
}
return 0;
}
G-说能过那是假的 o表示目前O的总数，or表示目前OR的总数，orz表示目前ORZ的总数 为O时，o++ 为R时, or+=o 为Z时，orz+=or 最终的orz即为所求
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1e5+5;
ll dp[5];
int main(){
string s;
cin>>s;
for(int i=0;i<s.length();i++){
if(s[i]=='Z') dp[3]+=dp[2];
if(s[i]=='R') dp[2]+=dp[1];
if(s[i]=='O') dp[1]+=1;
}
cout<<dp[3]<<endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
namespace fast{inline char nc(){static char buf[100000],*L=buf,*R=buf;return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;}template<class orz> inline void qread(orz &x){x=0;char ch=nc();bool f=0;while(ch<'0'||ch>'9')(ch=='-')&&(f=1),ch=nc();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=nc();f&&(x=-x);}}using namespace fast;
template<class orz>inline void read(orz &x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9')(ch=='-')&&(f=1),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();f&&(x=-x);}
template<class orz>inline void out(orz x){(x<0)&&(putchar('-'),x=-x);if(x>9)out(x/10);putchar(x%10+'0');}
#define inf 0x3f3f3f3f
#define ***(x) out(x),putchar(10)
#define space(x) out(x),putchar(32)
#define mem(a,b) memset(a,b,sizeof(a))
///******************************head*************************************///
const double eps=1e-9;const ll mod=1e9+7;//998244353;
const int M=1e2+7,N=1e5+7;
int T,n,m;
int unit;
struct node{
int l,r,id;
bool operator<(const node &p)const{
if(l/unit!=p.l/unit) return l/unit<p.l/unit;
return r<p.r;
}
}q[N];
ll inv[N],fac[N],ans[N],tmp,iv2[N];
ll Com(int x,int y) //Cx qu y
{
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
void init()
{
inv[0]=inv[1]=fac[0]=iv2[0]=1;
for(int i=1;i<N;i++)
fac[i]=fac[i-1]*i%mod,iv2[i]=iv2[i-1]*500000004ll%mod;
for(int i=2;i<N;i++)
inv[i]=ll(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<N;i++)
inv[i]=inv[i-1]*inv[i]%mod;
}
void addr(int r,int l)
{
tmp=(tmp*2-Com(r,l)+mod)%mod;
}
void addl(int l,int r)
{
tmp=(tmp+Com(r,l))%mod;
}
void dell(int l,int r)
{
tmp=(tmp-Com(r,l)+mod)%mod;
}
void delr(int r,int l)
{
tmp=(tmp+Com(r,l))%mod;
tmp=tmp*inv[2]%mod;
}
int main()
{
init();
int cas=0;read(n);
unit=sqrt(n);
for(int i=1;i<=n;i++)
read(q[i].r),read(q[i].l),q[i].id=i;
sort(q+1,q+1+n);
tmp=2;
int l=1,r=1;
for(int i=1;i<=n;i++){
while(r<q[i].r) addr(r++,l);
while(r>q[i].r) delr(--r,l);
while(l<q[i].l) addl(++l,r);
while(l>q[i].l) dell(l--,r);
ans[q[i].id]=tmp*iv2[q[i].r]%mod;
}
for(int i=1;i<=n;i++)
***(ans[i]);
return 0;
}
J-滑稽树下你和我 将一条边删去后，分成的两棵子树内的点都需要经过这条边才能到达另一棵子树，它对结果的贡献为 左端结点个数∗右端节点个数∗权值
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
namespace fast{inline char nc(){static char buf[100000],*L=buf,*R=buf;return L==R&&(R=(L=buf)+fread(buf,1,100000,stdin),L==R)?EOF:*L++;}template<class orz> inline void qread(orz &x){x=0;char ch=nc();bool f=0;while(ch<'0'||ch>'9')(ch=='-')&&(f=1),ch=nc();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=nc();f&&(x=-x);}}using namespace fast;
template<class orz>inline void read(orz &x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9')(ch=='-')&&(f=1),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();f&&(x=-x);}
template<class orz>inline void out(orz x){(x<0)&&(putchar('-'),x=-x);if(x>9)out(x/10);putchar(x%10+'0');}
#define inf 0x3f3f3f3f
#define ***(x) out(x),putchar(10)
#define space(x) out(x),putchar(32)
#define mem(a,b) memset(a,b,sizeof(a))
///******************************head*************************************///
const double eps=1e-9;const ll mod=1e9+7;//998244353;
const int M=1e2+7,N=1e5+7;
int head[N<<1],nxt[N<<1],to[N<<1],tot;
ll val[N<<1],siz[N],n,ans;
void init()
{
mem(head,-1),tot=0,ans=0;
}
void addedge(int u,int v,ll w)
{
to[tot]=v,val[tot]=w,nxt[tot]=head[u],head[u]=tot++;
to[tot]=u,val[tot]=w,nxt[tot]=head[v],head[v]=tot++;
}
void dfs(int cur,int pre)
{
siz[cur]=1;
for(int i=head[cur];~i;i=nxt[i])if(to[i]!=pre){
dfs(to[i],cur);
siz[cur]+=siz[to[i]];
ans=(ans+siz[to[i]]*(n-siz[to[i]])%mod*val[i]%mod)%mod;
}
}
int main()
{
read(n);
init();
ll z;
for(int i=1,x,y;i<n;i++){
read(x),read(y),read(z);
addedge(x,y,z);
}
dfs(1,-1);
***(ans);
return 0;
}
K-白山茶与红玫瑰 线段树维护区间前缀连续0/1、后缀连续0/1、区间最大连续0/1 因为偶数次翻转相当于没变，异或更新lazy标记 查询 左子树最大连续01、右子树最大连续01、左后缀+右前缀 三者取最大
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<set>
#define MAX_V 10000
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double PI=acos(-1);
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const int maxn=1e5+5;
struct node{
int l,r;
int lm0,rm0,m0,add;
int lm1,rm1,m1;
}s[maxn*4];
int a[maxn];
int n,m;
inline void PushUp(int p){
if(s[p<<1].lm0 == s[p<<1].r-s[p<<1].l+1){
s[p].lm0=s[p<<1].lm0+s[p<<1|1].lm0;
}else s[p].lm0=s[p<<1].lm0;
if(s[p<<1].lm1==s[p<<1].r-s[p<<1].l+1){
s[p].lm1=s[p<<1].lm1+s[p<<1|1].lm1;
}else s[p].lm1=s[p<<1].lm1;
if(s[p<<1|1].rm0==s[p<<1|1].r-s[p<<1|1].l+1){
s[p].rm0=s[p<<1].rm0+s[p<<1|1].rm0;
}else s[p].rm0=s[p<<1|1].rm0;
if(s[p<<1|1].rm1==s[p<<1|1].r-s[p<<1|1].l+1){
s[p].rm1=s[p<<1].rm1+s[p<<1|1].rm1;
}else s[p].rm1=s[p<<1|1].rm1;
s[p].m0=max(s[p<<1].m0,s[p<<1|1].m0);
s[p].m0=max(s[p].m0,s[p<<1].rm0+s[p<<1|1].lm0);
s[p].m1=max(s[p<<1].m1,s[p<<1|1].m1);
s[p].m1=max(s[p].m1,s[p<<1].rm1+s[p<<1|1].lm1);
}
void build(int p,int l,int r){
s[p].l=l,s[p].r=r;
if(l==r){
if(a[l]==0){
s[p].lm0=s[p].rm0=s[p].m0=1;
}else{
s[p].lm1=s[p].rm1=s[p].m1=1;
}
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
PushUp(p);
}
void spread(int p){
if(s[p].add){
swap(s[p<<1].lm0,s[p<<1].lm1);
swap(s[p<<1].rm0,s[p<<1].rm1);
swap(s[p<<1].m0,s[p<<1].m1);
swap(s[p<<1|1].lm0,s[p<<1|1].lm1);
swap(s[p<<1|1].rm0,s[p<<1|1].rm1);
swap(s[p<<1|1].m0,s[p<<1|1].m1);
s[p<<1].add^=1;
s[p<<1|1].add^=1;
s[p].add=0;
}
}
void change(int p,int l,int r){
if(l<=s[p].l&&s[p].r<=r){
swap(s[p].lm0,s[p].lm1);
swap(s[p].rm0,s[p].rm1);
swap(s[p].m0,s[p].m1);
s[p].add^=1;
return;
}
spread(p);
int mid=(s[p].l+s[p].r)>>1;
if(l<=mid) change(p<<1,l,r);
if(r>mid) change(p<<1|1,l,r);
PushUp(p);
}
int ask(int p,int l,int r){
if(s[p].l>=l&&s[p].r<=r){
return s[p].m1;
}
spread(p);
int mid=(s[p].l+s[p].r)>>1;
if(r<=mid) return ask(p<<1,l,r);
if(l>mid) return ask(p<<1|1,l,r);
int lv,rv,rlv=0;
lv=ask(p<<1,l,r);
rv=ask(p<<1|1,l,r);
rlv=min(mid-l+1,s[p<<1].rm1)+min(r-mid,s[p<<1|1].lm1);
rlv=max(rlv,max(lv,rv));
return rlv;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,1,n);
scanf("%d",&m);
while(m--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1){
change(1,x,y);
}else{
printf("%d\n",ask(1,x,y));
}
}
return 0;
}
投递西门子等公司7个岗位 >