zkw 뉴 번 막 아 주세요. 그리고 fread 는 정말 빠르다.
제목:
http://www.lydsy.com/JudgeOnline/problem.php?id=4373
대의:n 의 수열 을 드 리 겠 습 니 다.매번 구간[l,r]안의 숫자 정렬 을 조회 한 후에 공차 가 k 인 등차 수열 을 구성 하 는 지 여 부 를 확인 합 니 다.수정 작업 도 있 습 니 다.
사고방식:어 려 운 점 은 등차 수열 의 구성 여 부 를 판단 하 는 데 있다.우 리 는 제곱 과 의 방식 으로 Hash 를 한 번 한 다음 에 등차 수열 제곱 과 공식 이 계산 한 값 을 비교 할 수 있다.만약 일치 하지 않 는 다 면 그 중의 수가 다르다 는 것 을 설명 할 수 있다.즉,등차 수열 을 구성 하지 않 는 다 는 것 이다.그 다음 엔 트 리 가 난 장 판 이 었 어 요.
이것 은 내 가 보기에 가장 명확 하 게 쓴 zkw 선분 트 리 의 소개(튜 토리 얼)이다.그럼요.
클릭 하여 링크 열기
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 300010;
const int INF = 0x3f3f3f3f;
int bas = 1;
struct seg {
int mn;ll sum2;
}t[maxn << 2];
char * cp=(char *)malloc(20000000);
void in(int &x){
while(*cp'9')++cp;
for(x=0;*cp>='0'&&*cp<='9';)x=x*10+(*cp++^'0');
}
inline void pushup(int n)
{
t[n].mn = min(t[n << 1].mn, t[n << 1 | 1].mn);
t[n].sum2 = t[n << 1].sum2 + t[n << 1 | 1].sum2;
}
void build(int n)
{
while (bas < (n + 2))//
bas <<= 1;
for (int i = bas + 1;i <= bas + n;i++)
{
in(t[i].mn);t[i].sum2 = t[i].mn *t[i].mn * 6;// 6 6，
}
for (int i = bas - 1;i > 0;i--)
pushup(i);
}
void update(int n, int val)
{
n += bas;
t[n].mn = t[n].sum2 = val;
t[n].sum2 = t[n].sum2 * t[n].sum2 * 6;
for (n >>= 1;n > 0;n >>= 1) //
pushup(n);
}
ll qsum(int l, int r)
{
ll ans = 0;
for (l += bas - 1, r += bas + 1;l^r ^ 1;l >>= 1, r >>= 1)
{
if ((~l) & 1)ans = ans + t[l ^ 1].sum2; // sum
if (r & 1)ans =ans + t[r ^ 1].sum2; // sum
}
return ans;
}
int qmin(int l, int r)
{
int ans = INF;
for (l += bas - 1, r += bas + 1;l^r ^ 1;l >>= 1, r >>= 1)
{
if ((~l) & 1)ans = min(ans, t[l ^ 1].mn);
if (r & 1)ans = min(ans, t[r ^ 1].mn);
}
return ans;
}
int main()
{
int n, m, opt, l, r, k, cnt = 0;
fread(cp,1,20000000,stdin);
in(n);in(m);
build(n);
while (m--)
{
in(opt);in(l);in(r);
l ^= cnt, r ^= cnt;
if (opt == 2)
{
in(k);
k ^= cnt;
int sum = qsum(l, r), mm = qmin(l, r), len = r- l;
if (sum == mm*mm*(len + 1) * 6 + len*(len + 1)*mm*k * 6 + len*(len + 1)*(len << 1 | 1)*k*k)
{
cnt++;printf("Yes
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ 4373 산수 천재 ⑨ 등차 수열 학습 zkw 선분 트 리
zkw 뉴 번 막 아 주세요.
그리고 fread 는 정말 빠르다.
제목:
http://www.lydsy.com/JudgeOnline/problem.php?id=4373
대의:n 의 수열 을 드 리 겠 습 니 다.매번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
