블록, 모 팀 알고리즘 총화
블록 을 나 누 는 것 은 일종 의 폭력 알고리즘 이지 만 복잡 도가 폭력 보다 좋 고 충분 한 예비 처리 와 합 리 적 이 고 실행 가능 한 유지 작업 을 바탕 으로 최적화 시간 을 하 는 것 이다.
예비 처리 + 유지 보수 의 소모 시간 과 폭력 처리 의 소모 시간 에서 균형 을 찾 아 이 아름 다운 알고리즘 을 만 들 었 습 니 다.
표지: 특정한 구간 내 요소 의 종류 수 를 조회 하고 특정한 구간 이 특정한 요소 와 같은 수의 개수 (즉 순위) 를 조회 합 니 다.
템 플 릿: LuoguP 2801 교주 의 마법
C 와 같은 개 수 를 조회 하기 위해 정렬 할 수 있 으 며 구간 길이 - C 의 순위 가 답 수 입 니 다.
그래서 블록 내 질서 있 는 배열 을 동적 으로 유지 할 수 있 습 니 다.
#include
#define re register
#define inc(i,j,k) for(re int i=j;i<=k;++i)
#define il inline
using namespace std;
const int maxn=1000010;
vector <int> ve[1010];
int v[maxn],bl[maxn],atag[maxn];
int n,m,base;
il void reset(int x) //
{
ve[x].clear();
inc(i,(x-1)*base+1,min(x*base,n)) ve[x].push_back(v[i]);// n
sort(ve[x].begin(),ve[x].end());
}
il void add(int a,int b,int c)//
{
inc(i,a,min(bl[a]*base,b)) v[i]+=c;//
reset(bl[a]);
if(bl[a]!=bl[b]) {inc(i,(bl[b]-1)*base+1,b) v[i]+=c; reset(bl[b]);}//
inc(i,bl[a]+1,bl[b]-1) atag[i]+=c;
}
il int query(int a,int b,int c)//
{
int ans=0;
inc(i,a,min(bl[a]*base,b)) if(v[i]+atag[bl[a]]; //
if(bl[a]!=bl[b])
{
inc(i,(bl[b]-1)*base+1,b) if(v[i]+atag[bl[b]];//
}
inc(i,bl[a]+1,bl[b]-1)// , lazy_tag
{
int x=c-atag[i];
ans+=lower_bound(ve[i].begin(),ve[i].end(),x)-ve[i].begin();// x
}
return ans;
}
int main()
{
scanf("%d %d",&n,&m);
base=sqrt(n);
inc(i,1,n) scanf("%d",&v[i]),bl[i]=(i-1)/base+1,ve[bl[i]].push_back(v[i]);
inc(i,1,bl[n]) sort(ve[i].begin(),ve[i].end());
char s;
re int x,y,z;
inc(i,1,m)
{
s=getchar();
while(s!='A'&&s!='M') s=getchar();
if(s=='M')
{
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
}
else
{
scanf("%d %d %d",&x,&y,&z);
printf("%d
",y-x+1-query(x,y,z));
}
}
}
다른 예 제 는 우선 생각해 보 자
그리고...
막 대
모 팀 도 사실은 블록 을 나 누 는 알고리즘 을 바탕 으로 하 는데 주로 사상 이 라 고 생각 합 니 다. 저 는 질문 문제 에 대한 오프라인 처 리 를 바탕 으로 일정한 순서에 따라 문 제 를 처리 하 는 것 이 라 고 생각 합 니 다.
그리고 폭력의 복잡 도 를 보장 했다.
구체 적 인 실현 은 왼쪽 구간 의 블록 에 따라 정렬 하고 빠 르 고 똑 같이 오른쪽 점 에 따라 정렬 하 며 같은 블록 안의 복잡 도 O (n) 를 확보 하고 모두 sqrt (n) 블록 이 있 습 니 다.
그래서 총 복잡 도 O (n * sqrt (n))
주로 원소 의 종류 수 를 조회 하 는 데 쓰 인 다
템 플 릿: LuoguP 2709 작은 B 의 질문
#include
#define ll long long
#define re register
using namespace std;
#define maxn 50005
struct query
{
int l,r,id,pos;
// friend bool operator < (query xx,query yy)
// { if(xx.pos==yy.pos) return xx.l
bool operator const query &x) const {if(pos==x.pos)return r<x.r;
else return pos<x.pos;}
}a[maxn];
int b[maxn],n,m,K;ll cnt[maxn],Ans[maxn];
inline int read(){
int f=1,x=0;char ch;
do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
return x*f;
}
int main()
{
// freopen("testdata.in.txt","r",stdin);
// freopen("4321.txt","w",stdout);
n=read(); m=read(); K=read();
int siz=(int) sqrt(n);
for(re int i=1;i<=n;++i) b[i]=read();
for(re int i=1;i<=m;++i)
{
a[i].l=read(); a[i].r=read(); a[i].id=i;
a[i].pos=(a[i].l-1)/siz+1;
}
sort(a+1,a+m+1);
int l=1,r=0; long long ans=0;
for(re int i=1;i<=m;++i)
{
while(l>a[i].l) { l--; cnt[b[l]]++; ans+= 2*cnt[b[l]]-1 ;} // ,
while(r2*cnt[b[r]]-1 ;}
while (r > a [i]. r) {cnt [b [r]] --; ans - = 2 * cnt [b [r]] + 1; r -;} / / / 거 슬러 올 라 갈 때 통계 한 다음 가감
while(l2*cnt[b[l]]+1 ; l++; }
Ans[a[i].id]=ans;
}
for(re int i=1;i<=m;++i) printf("%lld",Ans[i]);
}
그 다음은 모 팀 에 대한 수정 작업 이다. 모 팀 과 원판 의 차 이 는 시간 축 이 많아 졌 다.
수정 작업 을 낡은 것 을 삭제 하고 새로운 것 을 추가 하 는 것 으로 간주 하 는 사상 은 많은 경우 에 사용 된다.
또한 누 드 폭력 입 니 다. 시간축 의 수정 이 무엇 을 했 는 지 에 만 관심 을 가 져 야 합 니 다. 이렇게 조회 할 때 현재 시간 전의 조작 만 고려 하면 됩 니 다.
블록 크기 (n * t) 1 / 3 복잡 도 O (n4 * t) 1 / 3) ->증명 할 줄 모르다
템 플 릿 문제 LuoguP 1903 색
/ / 와 로 골 은 갑자기 자신 이 제출 한 코드 를 볼 수 없 게 되 었 다...................................................................
#include
#include
#include
using namespace std;
#define fo(a,b,c) for(int a=b;a<=c;a++)
#define go(a,b,c) for(int a=b;a>=c;a--)
int read(){
int a=0,f=0;char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
for(;c>='0'&&c<='9';c=getchar())a=a*10+c-'0';
return f?-a:a;
}
const int N=10001;
int a[N],p[1000001],ans[N],divi;
struct nod{int pla,pre,suc;}cg[N];
struct node{int l,r,t,bel;}ls[N];
int cmp(node a,node b){
if(a.l/divi!=b.l/divi)return a.l/dividivi;
if(a.r/divi!=b.r/divi)return a.r/dividivi;
return a.t<b.t;
}
int main(){
int n=read(),m=read(),ln=0,tn=0,l=1,r=0,t=0,num=0;
fo(i,1,n)a[i]=read();
fo(i,1,m){
scanf("
");
if(getchar()=='R'){// ,
++tn;cg[tn].pla=read(),cg[tn].suc=read();
cg[tn].pre=a[cg[tn].pla];
a[cg[tn].pla]=cg[tn].suc;
}
else ls[++ln]=(node){read(),read(),tn,ln};
}
divi=ceil(exp((log(n)+log(tn))/3));//
go(i,tn,1)a[cg[i].pla]=cg[i].pre;
sort(ls+1,ls+ln+1,cmp);
fo(i,1,m){
while(ls[i].l;
while(ls[i].l>l)num-=!--p[a[l++]];//l
while(ls[i].r>r)num+=!p[a[++r]]++;
while(ls[i].r//r
while(ls[i].t<t){
int pla=cg[t].pla;
if(l<=pla&&pla<=r)num-=!--p[a[pla]];
a[pla]=cg[t--].pre;
if(l<=pla&&pla<=r)num+=!p[a[pla]]++;
};
while(ls[i].t>t){
int pla=cg[++t].pla;
if(l<=pla&&pla<=r)num-=!--p[a[pla]];
a[pla]=cg[t].suc;
if(l<=pla&&pla<=r)num+=!p[a[pla]]++;
};//t
ans[ls[i].bel]=num;
}
fo(i,1,ln)printf("%d
",ans[i]);
return 0;
}
2 차 오프라인 모 팀
updataing......
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.