(TIOJ) 1160 . 3.動態眾數問題

http://tioj.ck.tp.edu.tw/problems/1160

我是用數值線段樹下去硬做XDDD

我想應該還有更好的方法

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

const int MAX_N = 1e5+5;

struct Node {
 Node* lc;
 Node* rc;
 pair<int,int> val;
 Node() {
  lc=rc=NULL;
  val=make_pair(-1,-1);
 }
 void pull() {
  val=max(lc->val,rc->val);
 }
};

Node* Build(int L,int R) {
 Node* node=new Node();
 if (L==R) {
  return node;
 }
 int mid=(L+R)>>1;
 node->lc=Build(L,mid);
 node->rc=Build(mid+1,R);
 node->pull();
 return node;
}

void modify(Node* node,int L,int R,int pos,int Val) {
 if (L==R) {
  if (node->val.first==-1) node->val=make_pair(1,-Val);
  else node->val.first+=1;
  return;
 }
 int mid=(L+R)>>1;
 if (pos<=mid) modify(node->lc,L,mid,pos,Val);
 else modify(node->rc,mid+1,R,pos,Val);
 node->pull();
 return;
}

int num[MAX_N];
int pos[MAX_N];
vector<int> vec;

int main () {
 int i=0;
 while (scanf("%d",&num[i]) != EOF) {
  if (num[i]==0) break;
  vec.push_back(num[i]);
  i++;
 }
 sort(vec.begin(),vec.end());
 vec.resize(unique(vec.begin(),vec.end()) - vec.begin());
 for (int x=0;i>x;x++) {
  int tmp=num[x];
  pos[x] = lower_bound(vec.begin(),vec.end(),tmp) - vec.begin() + 1;
 }
 Node* root = Build(1,MAX_N);
 for (int x=0;i>x;x++) {
  modify(root,1,MAX_N,pos[x],num[x]);
  printf("%d %d\n",root->val.first,-root->val.second);
 }
}