C(clang 3.9) 解法, 执行用时: 496ms, 内存消耗: 196696K, 提交时间: 2018-12-15 19:10:09

#include<stdio.h>
int main (void)
{
    int n,m;
    scanf("%d%d",&n,&m);
    int i,j;
    char cs[n];
    char s[n];
    scanf("%s",cs);
    for(i=0;i<n;i++)
        if(cs[i]=='0')
            s[i]=0;
        else
            s[i]=1;
    int op[m+1][3];
    for(i=1;i<=m;i++){
        scanf("%d",&op[i][0]);
        if(op[i][0]==3)
            scanf("%d",&op[i][1]);
        else{
            scanf("%d%d",&op[i][1],&op[i][2]);
            op[i][1]--;
            op[i][2]--;
        }
    }
    
    char val[m+1][n];
    int k;
    int count;
    for(i=0;i<m+1;i++)
        for(j=0;j<n;j++)
            val[i][j]=2;
    for(i=0;i<n;i++)
        val[0][i]=s[i];
    for(i=1;i<=m;i++){
        switch(op[i][0]){
            case 1:
                for(j=op[i][1];j<=op[i][2];j++)
                    val[i][j]=0;
                break;
            case 2:
                for(j=op[i][1];j<=op[i][2];j++)
                    val[i][j]=1;
                break;
            case 3:
                for(j=0;j<n;j++)
                    val[op[i][1]][j]=2;
                break;
            case 4:
                count =0;
                for(j=op[i][1];j<=op[i][2];j++){
                    k=i;
                    while(val[k][j]==2)
                        k--;
                    if(val[k][j])
                        count++;
                }
                printf("%d\n",count);
                break;
        }
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 2102ms, 内存消耗: 972K, 提交时间: 2020-08-06 14:49:25

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

int i,j,n,m,l[20005],r[20005],op[20005],ans[20005];
char R[10005];
vector<pair<bool,int>>T;
int main()
{
	scanf("%d%d%s",&n,&m,R+1);
    for(i=0;i<m;i++)
	{
		scanf("%d%d",&op[i],&l[i]);
		if(op[i]!=3)scanf("%d",&r[i]);
	}
	for(i=1;i<=n;i++)
	{
		bool V[20005]={0};
		T.clear();
		for(j=0;j<m;j++)
		{
			if(op[j]!=3&&(l[j]>i||r[j]<i))continue;
			if(op[j]==1)T.push_back({0,j});
			if(op[j]==2)T.push_back({1,j});
			if(op[j]==3)V[l[j]-1]=1;
			while(T.size()&&V[T[T.size()-1].second])T.pop_back();
			if(op[j]==4)
			{
				if(T.size())ans[j]+=T[T.size()-1].first;
				else ans[j]+=R[i]-'0';
			}
		}
	}
	for(i=0;i<m;i++)if(op[i]==4)printf("%d\n",ans[i]);
    return 0;
}

C++(clang++11) 解法, 执行用时: 2204ms, 内存消耗: 243088K, 提交时间: 2021-03-07 19:58:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e4+5;
int n,m,f[N];
bool del[N];
char s[N];
stack<short>q[10001];
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int cas=1;cas<=m;cas++)
	{
		int opt;scanf("%d",&opt);
		if(opt==3)
		{
			int k;scanf("%d",&k);
			del[k]=true; 
		}
		else
		{
			int l,r;scanf("%d%d",&l,&r);
			if(opt<=2)
			{
				if(opt==1) f[cas]=0;
				else f[cas]=1;
				for(int i=l;i<=r;i++)
					q[i].push(cas);
			}
			else
			{
				int ans=0;
				for(int i=l;i<=r;i++)
				{
					while(q[i].size()&&del[q[i].top()]) q[i].pop();
					if(q[i].size()==0) ans+=s[i]-'0';
					else ans+=f[q[i].top()];
				}
				printf("%d\n",ans);
			}
		}
	}
}