QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #429565 | #440. 时代的眼泪 | SimonLJK | Compile Error | / | / | C++20 | 8.5kb | 2024-06-02 17:07:45 | 2024-06-02 17:07:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;#include<bits/stdc++.h>
using namespace std;
bool __st;
typedef long long ll;
const int N=1e5+99,M=2e5+99;
int n,m,p[N];
struct Q{
int x1,x2,y1,y2;
}q[M];
int bit[N];
void add(int x,int v){
while(x<N){
bit[x]+=v;
x+=(x&(-x));
}
return;
}
int que(int x){
int re=0;
while(x){
re+=bit[x];
x-=(x&(-x));
}
return re;
}
void solve1(){
int x1,x2,y1,y2; ll ans=0;
for(int i=1;i<=m;i++){
ans=0;
x1=q[i].x1; x2=q[i].x2; y1=q[i].y1; y2=q[i].y2;
for(int j=x1;j<=x2;j++){
if(p[j]<y1||p[j]>y2) continue;
ans+=que(p[j]); add(p[j],1);
}
cout<<ans<<'\n';
for(int j=x1;j<=x2;j++){
if(p[j]<y1||p[j]>y2) continue;
add(p[j],-1);
}
}
return;
}
bool judge(){
for(int i=1;i<=m;i++)
if(q[i].y1!=1||q[i].y2!=n) return false;
return true;
}
const int L=1009;
int B,cnt,bel[N],lp[N],rp[N];
ll num[L][L];
struct tree{
int val;
int ln,rn;
}tr[N*20];
int cntnode,rt[N];
void add(int &node,int pn,int l,int r,int tar){
node=++cntnode; tr[node]=tr[pn]; tr[node].val++;
if(l==r) return;
int mid=(l+r>>1);
if(tar<=mid) tr[node].ln=0,add(tr[node].ln,tr[pn].ln,l,mid,tar);
else tr[node].rn=0,add(tr[node].rn,tr[pn].rn,mid+1,r,tar);
}
void build(){
for(int i=1;i<=n;i++)
add(rt[i],rt[i-1],1,n,p[i]);
return;
}
int query(int node,int mnode,int l,int r,int tarl,int tarr){
if(tarl<=l&&r<=tarr) return tr[node].val-tr[mnode].val;
int re=0,mid=(l+r>>1);
if(tarl<=mid) re+=query(tr[node].ln,tr[mnode].ln,l,mid,tarl,tarr);
if(tarr>mid) re+=query(tr[node].rn,tr[mnode].rn,mid+1,r,tarl,tarr);
return re;
}
void solve2(){
B=120;
// cerr<<B<<endl;
for(int i=1;i<=n;i++){
bel[i]=(i-1)/B+1;
if(!lp[bel[i]]) lp[bel[i]]=i;
rp[bel[i]]=i;
}
cnt=bel[n];
ll ans=0;
for(int i=1;i<=cnt;i++){
ans=0;
for(int j=lp[i];j<=n;j++){
ans+=que(p[j]); add(p[j],1);
num[i][bel[j]]=ans;
}
for(int j=lp[i];j<=n;j++)
add(p[j],-1);
}
// cerr<<fixed<<setprecision(4)<<(double)clock()/CLOCKS_PER_SEC<<endl;
build();
// cerr<<fixed<<setprecision(4)<<(double)clock()/CLOCKS_PER_SEC<<endl;
int l,r;
for(int i=1;i<=m;i++){
l=q[i].x1; r=q[i].x2;
ans=num[bel[l]+1][bel[r]-1];
if(bel[l]==bel[r]){
for(int j=l;j<=r;j++){
ans+=query(rt[j],rt[l-1],1,n,1,p[j])-1;
}
}
else{
for(int j=lp[bel[r]];j<=r;j++)
ans+=query(rt[j],rt[lp[bel[l]+1]-1],1,n,1,p[j])-1;
for(int j=l;j<=rp[bel[l]];j++)
ans+=query(rt[r],rt[j-1],1,n,p[j],n)-1;
}
cout<<ans<<'\n';
}
return;
}
set<int> st;
set<int>::iterator it;
int cntt,id[100][2],ip[N];
void solve3(){
build();
for(int i=1;i<=n;i++)
ip[p[i]]=i;
for(int i=1;i<=n;i++){
st.insert(p[i]);
it=st.end(); it--;
while(*it!=p[i]){
cntt++;
id[cntt][0]=ip[*it]; id[cntt][1]=i;
it--;
}
}
int x1,x2,y1,y2; ll ans=0;
for(int i=1;i<=m;i++){
x1=q[i].x1; x2=q[i].x2; y1=q[i].y1; y2=q[i].y2;
ans=query(rt[x2],rt[x1-1],1,n,y1,y2);
ans=ans*(ans-1)/2;
// cout<<ans<<endl;
for(int j=1;j<=cntt;j++){
// cout<<id[j][0]<<" "<<id[j][1]<<endl;
if(id[j][0]<x1||id[j][1]>x2) continue;
if(p[id[j][0]]>y2||p[id[j][1]]<y1) continue;
ans--;
}
cout<<ans<<'\n';
}
}
bool __ed;
int main(){
// freopen("tears.in","r",stdin);
// freopen("tears.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=m;i++) cin>>q[i].x1>>q[i].x2>>q[i].y1>>q[i].y2;
if(n<=5000&&m<=5000) solve1();
else if(judge()) solve2();
else solve3();
// cerr<<fixed<<setprecision(4)<<(double)clock()/CLOCKS_PER_SEC<<endl;
// cerr<<fixed<<setprecision(4)<<(double)(&__st-&__ed)/(1<<20)<<"MB"<<endl;
return 0;
}
bool __st;
typedef long long ll;
const int N=1e5+99,M=2e5+99;
int n,m,p[N];
struct Q{
int x1,x2,y1,y2;
}q[M];
int bit[N];
void add(int x,int v){
while(x<N){
bit[x]+=v;
x+=(x&(-x));
}
return;
}
int que(int x){
int re=0;
while(x){
re+=bit[x];
x-=(x&(-x));
}
return re;
}
void solve1(){
int x1,x2,y1,y2; ll ans=0;
for(int i=1;i<=m;i++){
ans=0;
x1=q[i].x1; x2=q[i].x2; y1=q[i].y1; y2=q[i].y2;
for(int j=x1;j<=x2;j++){
if(p[j]<y1||p[j]>y2) continue;
ans+=que(p[j]); add(p[j],1);
}
cout<<ans<<'\n';
for(int j=x1;j<=x2;j++){
if(p[j]<y1||p[j]>y2) continue;
add(p[j],-1);
}
}
return;
}
bool judge(){
for(int i=1;i<=m;i++)
if(q[i].y1!=1||q[i].y2!=n) return false;
return true;
}
const int L=1009;
int B,cnt,bel[N],lp[N],rp[N];
ll num[L][L];
struct tree{
int val;
int ln,rn;
}tr[N*20];
int cntnode,rt[N];
void add(int &node,int pn,int l,int r,int tar){
node=++cntnode; tr[node]=tr[pn]; tr[node].val++;
if(l==r) return;
int mid=(l+r>>1);
if(tar<=mid) tr[node].ln=0,add(tr[node].ln,tr[pn].ln,l,mid,tar);
else tr[node].rn=0,add(tr[node].rn,tr[pn].rn,mid+1,r,tar);
}
void build(){
for(int i=1;i<=n;i++)
add(rt[i],rt[i-1],1,n,p[i]);
return;
}
int query(int node,int mnode,int l,int r,int tarl,int tarr){
if(tarl<=l&&r<=tarr) return tr[node].val-tr[mnode].val;
int re=0,mid=(l+r>>1);
if(tarl<=mid) re+=query(tr[node].ln,tr[mnode].ln,l,mid,tarl,tarr);
if(tarr>mid) re+=query(tr[node].rn,tr[mnode].rn,mid+1,r,tarl,tarr);
return re;
}
void solve2(){
B=120;
// cerr<<B<<endl;
for(int i=1;i<=n;i++){
bel[i]=(i-1)/B+1;
if(!lp[bel[i]]) lp[bel[i]]=i;
rp[bel[i]]=i;
}
cnt=bel[n];
ll ans=0;
for(int i=1;i<=cnt;i++){
ans=0;
for(int j=lp[i];j<=n;j++){
ans+=que(p[j]); add(p[j],1);
num[i][bel[j]]=ans;
}
for(int j=lp[i];j<=n;j++)
add(p[j],-1);
}
// cerr<<fixed<<setprecision(4)<<(double)clock()/CLOCKS_PER_SEC<<endl;
build();
// cerr<<fixed<<setprecision(4)<<(double)clock()/CLOCKS_PER_SEC<<endl;
int l,r;
for(int i=1;i<=m;i++){
l=q[i].x1; r=q[i].x2;
ans=num[bel[l]+1][bel[r]-1];
if(bel[l]==bel[r]){
for(int j=l;j<=r;j++){
ans+=query(rt[j],rt[l-1],1,n,1,p[j])-1;
}
}
else{
for(int j=lp[bel[r]];j<=r;j++)
ans+=query(rt[j],rt[lp[bel[l]+1]-1],1,n,1,p[j])-1;
for(int j=l;j<=rp[bel[l]];j++)
ans+=query(rt[r],rt[j-1],1,n,p[j],n)-1;
}
cout<<ans<<'\n';
}
return;
}
set<int> st;
set<int>::iterator it;
int cntt,id[100][2],ip[N];
void solve3(){
build();
for(int i=1;i<=n;i++)
ip[p[i]]=i;
for(int i=1;i<=n;i++){
st.insert(p[i]);
it=st.end(); it--;
while(*it!=p[i]){
cntt++;
id[cntt][0]=ip[*it]; id[cntt][1]=i;
it--;
}
}
int x1,x2,y1,y2; ll ans=0;
for(int i=1;i<=m;i++){
x1=q[i].x1; x2=q[i].x2; y1=q[i].y1; y2=q[i].y2;
ans=query(rt[x2],rt[x1-1],1,n,y1,y2);
ans=ans*(ans-1)/2;
// cout<<ans<<endl;
for(int j=1;j<=cntt;j++){
// cout<<id[j][0]<<" "<<id[j][1]<<endl;
if(id[j][0]<x1||id[j][1]>x2) continue;
if(p[id[j][0]]>y2||p[id[j][1]]<y1) continue;
ans--;
}
cout<<ans<<'\n';
}
}
bool __ed;
int main(){
// freopen("tears.in","r",stdin);
// freopen("tears.out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=m;i++) cin>>q[i].x1>>q[i].x2>>q[i].y1>>q[i].y2;
if(n<=5000&&m<=5000) solve1();
else if(judge()) solve2();
else solve3();
// cerr<<fixed<<setprecision(4)<<(double)clock()/CLOCKS_PER_SEC<<endl;
// cerr<<fixed<<setprecision(4)<<(double)(&__st-&__ed)/(1<<20)<<"MB"<<endl;
return 0;
}
詳細信息
answer.code:2:21: error: stray ‘#’ in program
2 | using namespace std;#include<bits/stdc++.h>
| ^
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:30: error: ‘bits’ was not declared in this scope
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
answer.code:2:35: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~
| std
answer.code:2:22: error: ‘include’ does not name a type
2 | using namespace std;#include<bits/stdc++.h>
| ^~~~~~~
answer.code:172:6: error: redefinition of ‘bool __st’
172 | bool __st;
| ^~~~
answer.code:4:6: note: ‘bool __st’ previously declared here
4 | bool __st;
| ^~~~
answer.code:174:11: error: redefinition of ‘const int N’
174 | const int N=1e5+99,M=2e5+99;
| ^
answer.code:6:11: note: ‘const int N’ previously defined here
6 | const int N=1e5+99,M=2e5+99;
| ^
answer.code:174:20: error: redefinition of ‘const int M’
174 | const int N=1e5+99,M=2e5+99;
| ^
answer.code:6:20: note: ‘const int M’ previously defined here
6 | const int N=1e5+99,M=2e5+99;
| ^
answer.code:175:5: error: redefinition of ‘int n’
175 | int n,m,p[N];
| ^
answer.code:7:5: note: ‘int n’ previously declared here
7 | int n,m,p[N];
| ^
answer.code:175:7: error: redefinition of ‘int m’
175 | int n,m,p[N];
| ^
answer.code:7:7: note: ‘int m’ previously declared here
7 | int n,m,p[N];
| ^
answer.code:175:9: error: redefinition of ‘int p [100099]’
175 | int n,m,p[N];
| ^
answer.code:7:9: note: ‘int p [100099]’ previously declared here
7 | int n,m,p[N];
| ^
answer.code:176:8...