求找错（悲）

常规
1

@ 蒟蒻·廖子阳，你是怎么4道题都做出来的

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[10000001];
int l,cnt;
int main(){
	cin>>n>>m;
	if(2*n<=m){
		cout<<0<<endl;
		return 0;
	}
	if(m==n+1){
		cout<<(m-3)*2+2<<endl;
		return 0;
	}
	for(int i=1;i<=m;i++){
		a[i]=1;
	}
	l=m-n;
	int k=0;
	for(int i=1;i<=m;i++){
		if(i%2==1){
			k++;
			a[i]=0;
		}
		if(k==l){
			break;
		}
	}
//	for(int i=1;i<=m;i++){
//		cout<<a[i]<<' ';
//	}
	for(int i=1;i<=m;i++){
		if(a[i]==1){
			if(i==1){
				if(a[m]==1){
					cnt++;
				}
				if(a[i+1]==1){
					cnt++;
				}
			}else if(i==m){
				if(a[1]==1){
					cnt++;
				}
				if(a[m-1]==1){
					cnt++;
				}
			}else{
				if(a[i-1]==1){
					cnt++;
				}
				if(a[i+1]==1){
					cnt++;
				}
			}
		}
		
	}
	cout<<cnt<<endl;
	return 0;
}

WA？
题目链接
第四题

#include<bits/stdc++.h>
using namespace std;
long long c,que;
queue<long long> q;
long long a[1000001];
int main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	cin>>c>>que;
	while(que--){
		int op;
		cin>>op;
		if(op==1){
			int x;
			cin>>x;
			for(int i=1;i<=x;i++){
				q.push(i);
			}
		}else if(op==2){
			int x;
			cin>>x;
			for(long long i=1;i<=x;i++){
				q.pop();
			}
		}else if(op==3){
			long long z,o=q.size();
			cin>>z;
			memset(a,0,sizeof a);
			for(long long i=1;i<=o;i++){
				a[i]=q.front();
				if(i==z){
					cout<<a[i]<<endl;
				}
				q.pop();
			}
			for(long long i=1;i<=o;i++){
				q.push(a[i]);
			}
		}else if(op==4){
			long long mx=INT_MIN,o=q.size();
			memset(a,0,sizeof a);
			for(long long i=1;i<=o;i++){
				a[i]=q.front();
				mx=max(a[i],mx);
				q.pop();
			}
			for(long long i=1;i<=o;i++){
				q.push(a[i]);
			}
			cout<<mx<<endl;
		}
	}
	return 0;
}
1 个赞
2

有人能帮我找找问题吗

1 个赞
3

这是我第四题的20代码

#include<bits/stdc++.h>
using namespace std;
queue<int>q;
int n,m,i,j,c,x,y,l;
int main()
{
	scanf("%d%d",&c,&n);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&x);
		if(x!=4) scanf("%d",&y);
		if(x==1)
		{
			for(j=1;j<=y;++j) q.push(j);
			l+=y;
		}
		if(x==2)
		{
			for(j=1;j<=y;++j) q.pop();
			l-=y;
		}
		if(x==3)
		{
			for(j=1;j<=l;++j)
			{
				if(j==y) printf("%d\n",q.front());
				q.push(q.front());
				q.pop();
			}
		}
		if(x==4)
		{
			m=0;
			for(j=1;j<=l;++j)
			{
				m=max(m,q.front());
				q.push(q.front());
				q.pop();
			}
			printf("%d\n",m);
		}
	}
	return 0;
}
1 个赞
4

第四题最好格式化一下

1 个赞
5

A 你先隔一个放一个，然后再任意放一个都会带来 4 的贡献，也可以dp

D 考虑数很多但是块很少，且每块在右端点才有贡献，故用平衡树（set）维护块，并记录左右端点，还需要类似手写队列维护队头队尾便于计算位置（说白了就是用set维护手写队列的块）

2 个赞
6

平衡树？？？是什么

1 个赞
7

此题中的平衡树可以被set代替

2 个赞
8

STL库里的？

1 个赞
9

是集合吗？

1 个赞
10

是的

没说完整，块用set维护，最大值用multiset维护

1 个赞
11

让我想想

1 个赞
12

但是那样时间不应该差不多嘛

1 个赞
13

需要优化吗

1 个赞
14

时间空间复杂度，应该和队列差不多啊

1 个赞
15

为啥？
块数是 \mathcal{O}(q)

插入/删除一次，所以是 \mathcal{O}(q\log q)

剩下的操作一次是 \mathcal{O}(\log q)

所以总复杂度是 \mathcal{O}(q\log q)

1 个赞
16

这个做法和std比起来还是比较抽象的

1 个赞
17

我还是给个代码吧，仅供参考

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int c,q,tail,head;
multiset<int>mx;
struct node{
    int l,r,rval;
    bool operator<(const node&o)const{
        return l<o.l;
    }
};
set<node>s;
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>c>>q;
    for(int i=1,op,x;i<=q;++i){
        cin>>op;
        if(op==1){
            cin>>x;
            s.insert(node{tail+1,tail+x,x});
            tail+=x;
            mx.insert(x);
        }else if(op==2){
            cin>>x;
            auto qr=--s.upper_bound(node{head+x,0,0});
            for(auto it=s.begin();it!=qr;++it){
                mx.erase(mx.find(it->rval));
            }
            s.erase(s.begin(),qr);
            if(head+x!=qr->r){
                node t=*qr;
                s.erase(qr);
                s.insert(node{head+x+1,t.r,t.rval});
            }else{
                mx.erase(mx.find(qr->rval));
                s.erase(qr);
            }
            head+=x;
        }else if(op==3){
            cin>>x;
            auto it=--s.upper_bound(node{head+x,0,0});
            cout<<it->rval-(it->r-head-x)<<'\n';
        }else{
            cout<<*mx.rbegin()<<'\n';
        }
    }
    return 0;
}
1 个赞
18

image
排序是吗？

1 个赞
19

是的

2 个赞
20

一道set模板叫队列

1 个赞