이산 화+선분 수
2397 단어 데이터 구조
분석:
매번 1 작업 은 시퀀스 밑 에 first second 를 추가 합 니 다.first 와 second 는 최대 1e9 의 데이터 입 니 다.매번 2 작업 문의 시퀀스 에서 first 에서 두 번 째 수의 합 입 니 다.
처음부터 선분 트 리 처럼 느껴 졌 습 니 다.입력 데이터 가 너무 커서 오프라인 처리 로 데 이 터 를 분산 시 킨 다음 에 선분 트 리 에 던 져 두 개의 배열 을 유지 할 수 있 습 니 다.
sum:구간 수의 값 의 합 num:구간 수의 수량 과 ,매번 물 어 보 는 first 와 second 에 대해 우 리 는 첫 번 째 와 두 번 째 가 각각 어떤 숫자 인지 찾 았 다.
만약 두 숫자 가 다르다 면,먼저 몇 개의 이 두 숫자 를 취 했 는 지 계산 해 보 세 요.두 숫자 사이 의 숫자 와 우 리 는 직접 선분 트 리 구간 으로 구 할 수 있 습 니 다.
Ac code:
#include
using namespace std;
typedef long long ll;
const int maxn=100001;
const ll mod=1e9+7;
struct Node{
ll x,y;
};
Node a[maxn];
int op[maxn];
ll b[maxn],sum[maxn<<2],num[maxn<<2],vis[maxn];
void update(ll pos,ll val,ll l,ll r,ll rt)
{
if(l==r){
sum[rt]=(sum[rt]+(b[pos]*val)%mod)%mod;
num[rt]+=val;
return;
}
ll mid=(l+r)>>1;
if(pos<=mid) update(pos,val,l,mid,rt<<1);
else update(pos,val,mid+1,r,rt<<1|1);
sum[rt]=(sum[rt<<1]+sum[rt<<1|1])%mod;
num[rt]=num[rt<<1]+num[rt<<1|1];
}
ll query(ll L,ll R,ll l,ll r,ll rt)/// [L,R]
{
if(L<=l&&r<=R){
return sum[rt]%mod;
}
ll mid=(l+r)>>1;
ll ans=0;
if(L<=mid) ans=(ans+query(L,R,l,mid,rt<<1))%mod;
if(mid=pos&&num[rt]-vis[r]>1;
if(pos<=num[rt<<1]) query1(pos,l,mid,rt<<1);
else query1(pos-num[rt<<1],mid+1,r,rt<<1|1);
}
ll query2(ll L,ll R,ll l,ll r,ll rt)/// [L,R]
{
if(L<=l&&r<=R)
return num[rt];
ll mid=(l+r)>>1;
ll ans=0;
if(L<=mid) ans=(ans+query2(L,R,l,mid,rt<<1));
if(mid 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
