20th [막 팀] czy 의 후궁
2591 단어 막 대
[제목 설명]:
지난번 에 czy 가 기계실 에서 그의 후궁 을 잘 배정 한 후에 그 는 그의 여동생 을 c 가지 로 나 눌 수 있다 는 것 을 발견 했다. 그 는 항상 이런 문 제 를 고려 했다. [l, r] 의 여동생 중에서 몇 가지 다른 유형의 여동생 을 고 를 수 있 습 니까?
주의: czy 가 매우 좀 비 이기 때문에 그 는 선택 한 여동생 유형 이 [l, r] 에서 나타 나 는 횟수 가 정 짝수 라 는 것 을 알 고 있 습 니 다.
질문 약술: n 개 수, m 회 질문, 매번 [l, r] 구간 에 몇 개의 수가 마침 짝수 가 나 타 났 습 니까?
【 설명 입력 】:
첫 줄 3 개의 정 수 는 n, c, m 를 나타 낸다.
두 번 째 줄 n 개, 각각 Ai 는 [1, c] 사이 에 Ai 유형의 여동생 을 표시 합 니 다.
다음 m 줄, 줄 당 두 개의 정수 l, r 는 [l, r] 구간 의 답 을 묻는다.
[출력 설명]:
m 줄 이 있어 서 i 번 째 질문 의 답 을 표시 합 니 다.
【 샘플 입력 】:
5 5 3
1 1 2 2 3
1 5
3 4
2 3
[샘플 출력]:
2
1
0
[시간 제한, 데이터 범위 및 설명]:
시간: 1s 공간: 256 M
1 - 4 조 n, m = 500, 2000, 5000, 10000, c = 1000
5 - 7 조 n, m = 20000, 30000, 40000, c = 10000
8 - 10 조 n, m = 50000, 80000, 100000, c = 100000
데이터 무 작위 생 성 보증
첫 번 째 막 팀 이 드디어 맞 았 다...마음 이 지치다
사실 이 알고리즘 은 이해 하기 쉽다.순 서 를 매기 고 반복 해서 계산 하 는 것 이다. 예 를 들 어 첫 번 째 는 2 에서 5, 두 번 째 는 1 에서 7 이 라면 2 에서 5 를 바탕 으로 왼쪽 을 1 로, 오른쪽 을 7 로 밀어 2 에서 5 의 결 과 를 얻 을 수 있다.
모 팀 의 정 수 는 그의 정렬 에 있다. 나 는 왜 시작 점 이 있 는 블록 에 따라 정렬 해 야 하 는 지 의문 이 들 었 다. 시작 점 에 따라 정렬 하 는 것 이 아니 라 시작 점 에 따라 정렬 해 야 하 는 지 의문 이 들 었 다. 예 를 들 어 L. 그래서 이렇게 복잡 도 는 n 근호 n 이다.
#include
#include
#include
#include
#include
#include
#include
#define Maxn 100005
using namespace std;
inline int Getint(){
int x=0,f=1;char ch=getchar();
while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;}
int a[Maxn],pos[Maxn],t[1000005],ans=0,Ans[Maxn];
struct node{int l,r,num;}w[Maxn];
bool cmp(node a,node b){
return (pos[a.l]==pos[b.l]?a.rw[i].l){//
l--;
t[a[l]]++;
if(t[a[l]]%2==0)ans++;
if(t[a[l]]%2==1&&t[a[l]]!=1)ans--;
}
while(lw[i].r){//
t[a[r]]--;
if(t[a[r]]%2==0&&t[a[r]]!=0)ans++;
if(t[a[r]]%2==1)ans--;
r--;
}
Ans[w[i].num]=ans;
}
for(int i=1;i<=m;i++)
cout<